# On Well-Structured Convex-Concave Saddle Point Problems and Variational
Inequalities with Monotone Operators

Anatoli Juditsky LJK, Université Grenoble Alpes, 700 Avenue Centrale, 38401
Domaine Universitaire de Saint-Martin-d’Hères, France, anatoli.juditsky@univ-
grenoble-alpes.fr Arkadi Nemirovski ISyE, Georgia Institute of Technology,
Atlanta, Georgia 30332, USA<EMAIL_ADDRESS>
###### Abstract

For those acquainted with CVX (aka disciplined convex programming) of M. Grant
and S. Boyd [9], the motivation of this work is the desire to extend the scope
of CVX beyond convex minimization—to convex-concave saddle point problems and
variational inequalities with monotone operators. To attain this goal, given a
family ${\cal K}$ of cones (e.g., Lorentz, semidefinite, geometric, etc), we
introduce the notions of ${\cal K}$-conic representation of a convex-concave
saddle point problem and of variational inequality with monotone operator. We
demonstrate that given such a representation of the problem of interest, the
latter can be reduced straightforwardly to a conic problem on a cone from
${\cal K}$ and thus can be solved by (any) solver capable to handle conic
problems on cones from ${\cal K}$ (e.g., Mosek or SDPT3 in the case of
semidefinite cones). We also show that ${\cal K}$-representations of convex-
concave functions and monotone vector fields admit a fully algorithmic
calculus which helps to recognize the cases when a saddle point problem or
variational inequality can be converted into a conic problem on a cone from
${\cal K}$ and to carry out such conversion.

##  1 Introduction

Along with emergence of powerful computational tools, one of important
components of what is sometimes referred to as Interior-Point Revolution in
Convex Optimization was the rise of (informal) notion of a “well-structured
convex problem”—convex optimization problem which can be reformulated as a
conic problem on a cone from a “nice” family ${\cal K}$, most notably, the
families of finite direct products of nonnegative rays (Linear Programming),
Lorentz cones (Second Order Conic Programming), and semidefinite cones
(Semidefinite Programming). Problems of the latter “magic families” cover
basically all needs arising in applications of Convex Optimization to decision
making, engineering, statistics, etc. At the same time, reformulating problem
of interest as LP/SOCP/SDP makes the problem amenable for numerical processing
by a “universal” SDP solver, so that end user should not care much about
number-crunching. Today, there exist powerful universal SDP solvers such as
SDPT3 [19] or industrial-grade Mosek [2], with permanently improving
performance and reliability.

The “maiden form” of an optimization problem arising in applications usually
is not the “nice conic” one, even when at the end of the day the problem can
be cast into, say, an SDP program. Such transformation is carried out with the
help of a special “calculus” (see, e.g., [3, 4, 5]) which allows to recognize
that the problem at hand can be reformulated as, say, an SDP. This calculus,
as any other, has two components: (a) “raw materials”—a collection of sets and
functions possessing explicit representations via SDP (what exactly
“representation” means, will be explained in Section 2), and (b) “calculus
rules” expressing SDP representation of the result of a specific operation
with functions/sets via SDP representations of the operands. It turns out that
calculus rules for SDP representations cover all basic convexity-preserving
operations with functions (like taking linear combinations with nonnegative
coefficients and convexity-preserving compositions) and sets (like taking
finite intersections and images/inverse images under affine mappings).
Moreover, the calculus rules happen to be fully algorithmic and thus can be
implemented on a compiler. This possibility is utilized, for instance, in the
CVX software of M. Grant and S. Boyd [9] which is the second-to-none in terms
of its scope and user-friendliness tool for numerical processing of convex
optimization problems.

So far, we were speaking about (constrained) convex minimization, and this is
the usual scope of the calculus of well-structured convex problems. For
example, given a number of SDP-representable functions, the calculus allows to
obtain SDP representation of their maximum and thus convert to SDP program, in
an automated fashion, the problem of minimizing this maximum over a feasible
set given by an SDP representation. However, such calculus does not allow to
get an SDP representation of the maximum of infinite family of SDP-
representable functions, even when this family is perfectly well organized. As
a result, convex-concave saddle point problems, well-structured from the
“viewpoint of a human,” cannot be “fed to CVX” as they are, and reducing such
a problem to the conic form amenable for the existing powerful convex
optimization software requires ad hoc work on case-to-case basis. Similar
difficulties arise when instead of convex-concave saddle point problems
someone is looking to solve numerically other problems with convex structure,
most notably, variational inequalities (VI) with monotone operators. Monotone
VI’s can be thought of as the most general problems with convex structure: on
one hand, other problems of this type (constrained convex minimization,
convex-concave saddle points, convex Nash equilibrium problems) under
extremely mild boundedness and regularity assumptions can be reduced to
monotone VI’s (for details, see e.g., [5, Section 5.6]). On the other hand,
efficient black box oriented algorithms of convex minimization, like First
Order or Ellipsoid methods, can be extended to monotone VI’s (cf., e.g., [14])
without harming their efficiency estimates. There exists also rich literature
on extending polynomial time Interior-Point algorithms onto linear and
monotone complementarity problems, see, e.g., [11, 12, 7, 16, 17, 18] and
references therein. In particular, it is well known that VI with affine
monotone operator and domain admitting conic representation can be
straightforwardly reduced to a conic optimization problem. In [13, Section
7.4] this fact was somehow extended to nonlinear monotone VI’s from certain
restricted class—those admitting an explicit “convex representation” allowing
to reduce the VI of interest to an affine monotone VI on a properly modified
domain; that reference develops also a rudimentary calculus of convex
representations of monotone VI’s. Some results111dealing with the search for
strong solutions to VI’s with not necessarily monotone operator $F$ under
rather restrictive assumptions that $x^{T}F(x)$ and $-F(x)$ are convex on
polyhedral set ${\cal X}\subset{\mathbf{R}}^{n}_{+}$ on reformulations of VI’s
as convex optimization problems can be found in [1]. That being said, to the
best of our knowledge, beyond the classes of VI’s with affine monotone
operators and related bilinear saddle point problems there is no much
understanding of what is a “well structured” convex-concave saddle point
problem or “genuine”—not potential—monotone VI, and of how such a problem
should be represented in order for the representation to admit a meaningful
algorithmic calculus, on one hand, and to allow for straightforward conversion
of the problem into a nice conic program, say, SDP one, on the other.

The goal of what follows is to introduce the notion of “conic representations”
of problems with convex structure, specifically, convex-concave saddle point
problems and monotone VI’s, via a given family ${\cal K}$ of cones (e.g.,
direct products of nonnegative rays/Lorentz/Semidefinite cones). As we will
see, given such a representation, the problem of interest can be
straightforwardly converted to a conic problem on a cone from ${\cal K}$, and
representations in question admit a fully algorithmic calculus, similar to the
calculus of conic representations of convex functions/sets. In Section 3 we
develop conic representations of convex-concave functions, and then in Section
4 extend this framework to representations of monotone vector fields.
Derivations in Section 4 can be viewed as a “well-structured” (i.e., conic
representation-oriented) version of convex representation of a monotone
operator introduced in [13, Section 7.4].

##  2 Preliminaries

Consider a family ${{\cal K}}$ of regular (i.e., closed, convex, pointed, and
with nonempty interior) cones in Euclidean spaces such that the family

  1. 1.

contains nonnegative ray,

  2. 2.

is closed w.r.t. taking finite direct products of its members, and

  3. 3.

is closed w.r.t. passing from a cone to its dual.

From now on we adopt the following convention: we operate with once for ever
fixed family ${\cal K}$ of cones satisfying Assumptions 1–3, and whenever in
the sequel we consider a cone, say ${\mathbf{K}}$, this cone is assumed to
belong to ${\cal K}$. Besides this, ${\mathbf{K}}^{*}$ stands for the cone
dual to ${\mathbf{K}}$.

$\bullet$ Given a cone ${\mathbf{K}}\in{\cal K}$ we call a constraint in
variables $x\in{\mathbf{R}}^{n}$ of the form

$Ax\leq_{{\mathbf{K}}}a$ (1)

${\cal K}$-conic; as usual, $a\leq_{{\mathbf{K}}}b$ means that
$b-a\in{\mathbf{K}}$. Note that a system

$A_{k}x\leq_{{\mathbf{K}}_{k}}a_{k},1\leq k\leq K,$

of finitely many ${\cal K}$-conic constraints is equivalent to a single ${\cal
K}$-conic constraint222We follow the “Matlab convention” for matrices: $[A,B]$
and $[A;B]$ denote, respectively, the horizontal and vertical concatenations
of two matrices of compatible dimensions.

$[A_{1};...;A_{K}]x\leq_{{\mathbf{K}}}[a_{1};...;a_{K}]$

where ${\mathbf{K}}={\mathbf{K}}_{1}\times...\times{\mathbf{K}}_{K}$ belongs
to ${{\cal K}}$ along with ${\mathbf{K}}_{k}$, $k\leq K$, since ${{\cal K}}$
is closed w.r.t. taking direct products. For similar reasons, augmenting a
${\cal K}$-conic constraint $Ax\leq_{{\mathbf{K}}}a$ in variables $x$ by a
system $S$ of finitely many linear equalities and nonstrict linear equalities,
we get a conic constraint on $x$. Indeed, $S$ can be written equivalently as
$Bx\leq b$, so that the augmented constraint reads

$[A;B]x\leq_{{\mathbf{K}}\times{\mathbf{R}}^{m}_{+}}[a;b],\,\,m=\dim b,$

and the cone ${\mathbf{K}}\times{\mathbf{R}}^{m}_{+}$ belongs to ${{\cal K}}$
since the latter family contains ${\mathbf{K}}$, ${\mathbf{R}}_{+}$ and is
closed w.r.t. taking finite direct products.

$\bullet$ We call conic constraint (1) essentially strictly feasible, if
${\mathbf{K}}$ can be decomposed as
${\mathbf{K}}={\mathbf{R}}^{m}_{+}\times{\mathbf{L}}$ with regular cone
${\mathbf{L}}$, so that (1) is of the form

$[P;Q]x\leq_{{\mathbf{R}}^{m}_{+}\times{\mathbf{L}}}\leq[p;q],$

and there exists $\bar{x}$ such that $P\bar{x}\leq p$ and
$Q\bar{x}<_{{\mathbf{L}}}q$, the latter meaning that $q-Q\bar{x}\in\hbox{\rm
int}\,{\mathbf{L}}.$

$\bullet$ We say that a set $X\subset{\mathbf{R}}^{n}$ is ${\cal
K}$-representable if for properly selected $A,B,c$ and ${\mathbf{K}}\in{\cal
F}$ one has

$X=\\{x:\exists u:Ax+Bu\leq_{{\mathbf{K}}}c\\};$

whenever this is the case, the ${\cal K}$-conic constraint
$Ax+Bu\leq_{{\mathbf{K}}}c$ in the right hand side is called ${\cal
K}$-representation of $X$. We call a function
$f:{\mathbf{R}}^{n}\to{\mathbf{R}}\cup\\{+\infty\\}$ ${\cal K}$-representable
if the epigraph ${\hbox{\rm Epi}}\\{f\\}=\\{(x,t):t\geq f(x)\\}$ is ${\cal
K}$-representable and we refer to a ${\cal K}$-representation of ${\hbox{\rm
Epi}}\\{f\\}$ as the ${\cal K}$-representation of $f$. In other words,
asserting that ${\cal K}$-conic constraint $Ax+tb+Bu\leq_{{\mathbf{K}}}c$
represents $f$ is the same as saying that the following equivalence takes
place:

$t\geq f(x)\Leftrightarrow\exists u:Ax+tb+Bu\leq_{{\mathbf{K}}}c.$

Observe that the level sets $\\{x:f(x)\leq a\\}$, $a\in{\mathbf{R}}$, of
${\cal K}$-representable function $f$ are ${\cal K}$-representable:

$\left\\{t\geq f(x)\Leftrightarrow\exists
u:Ax+tb+Bu\leq_{{\mathbf{K}}}c\right\\}\Rightarrow\\{x:f(x)\leq
a\\}=\\{x:\exists u:Ax+By\leq_{{\mathbf{K}}}c-ab\\}.$

Thus, given ${\cal K}$-representations $\\{x:\exists
u:Ax+Bu\leq_{{\mathbf{K}}}c\\}$ of $X\subset{\mathbf{R}}^{n}$ and $\\{t\geq
f(x)\Leftrightarrow\exists v:Cx+td+Ev\leq_{{\mathbf{L}}}g\\}$ of
$f:{\mathbf{R}}^{n}\to{\mathbf{R}}\cup\\{+\infty\\}$, the problem

$\min_{x\in X}f(x)$ $None$

is equivalent to the conic problem

$\min_{x,t,u,v}\left\\{t:[Ax+Bu;Cx+td+Ev]\leq_{{\mathbf{K}}\times{\mathbf{L}}}[c;g]\right\\}$
$None$

on a cone from ${\cal K}$, where equivalence of $({\cal P})$ and $({\cal Q})$
precisely means that $x$ is a feasible solution to $({\cal P})$ with a finite
value of the objective if and only if there exist $t,u,v$ such that $t\geq
f(x)$ and $x,t,u,v$ is feasible for $({\cal Q})$.

${\cal K}$-representable functions/sets admit fully algorithmic calculus: all
basic convexity-preserving operations with sets and functions, (e.g., taking
finite intersections, images/inverse images under affine mappings, and direct
products of sets, or taking linear combinations with nonnegative coefficients
and convexity-preserving compositions of functions) as applied to ${\cal
K}$-representable operands, produce ${\cal K}$-representable results, with
representations of the results readily given by those of the operands; for
details, see, e.g., [4, 5]. When a solver for conic problems on cones from
${\cal K}$ is available, this calculus allows one to recognize that in the
problem $({\cal P})$ of interest objective $f$ and domain $X$ are ${\cal
K}$-representable and find the corresponding ${\cal
K}$-representations,333Note that calculus rules are fully algorithmic and thus
can be implemented by a compiler, the most famous example being the CVX
software [9] which can handle “semidefinite representability” (family ${\cal
K}$ comprised of direct products of semidefinite cones), and as a
byproduct—conic quadratic representability. so the problem of interest can be
converted into a conic problem $({\cal Q})$ on a cone from ${\cal K}$ and
solved by the solver at hand.

From now on, we operate with a once for ever fixed family ${\cal K}$ of cones
satisfying the above Assumptions 1–3, which allows for the convention as
follows: whenever in the sequel a cone arises, this cone, if the otherwise is
explicitly stated, belongs to ${\cal K}$. Besides this, ${\mathbf{K}}^{*}$
stands for the cone dual to ${\mathbf{K}}$.

##  3 Well-structured convex-concave saddle point problems

As far as its paradigm and set of rules are concerned,“calculus of ${\cal
K}$-representability” for, say, ${\cal K}$ specified as $\cal{SDP}$ (finite
direct products of semidefinite cones) covers all “basic” needs of “well-
structured” convex minimization. There is, however, an exception— the case in
which the objective in the convex problem of interest

$\min_{x\in{\cal X}}\overline{\Psi}(x)$ $None$

is given implicitly:

$\overline{\Psi}(x)=\sup_{y\in{\cal Y}}\psi(x,y)$ (2)

where ${\cal Y}$ is convex set and $\psi:{\cal X}\times{\cal
Y}\to{\mathbf{R}}$ is convex-concave (i.e., convex in $x\in{\cal X}$ and
concave in $y\in{\cal Y}$) and continuous. Problem $(P)$ with objective given
by (2) is called “primal problem associated with the convex-concave saddle
point problem $\min_{x\in{\cal X}}\max_{y\in{\cal Y}}\psi(x,y)$,” and problems
of this type do arise in some applications of well-structured convex
optimization. We are about to define a saddle point version of ${\cal
K}$-representability along with the corresponding calculus which allows to
convert “${\cal K}$-representable convex-concave saddle point problems” into
usual conic problems on cones from ${\cal K}$.

###  3.1 Conic representability of convex-concave function—definition

Let ${\cal X}$, ${\cal Y}$ be nonempty convex sets given by ${\cal
K}$-representations:

${\cal X}=\\{x:\exists\xi:Ax+B\xi\leq_{{\mathbf{K}}_{\cal X}}c\\},\,\,{\cal
Y}=\\{y:\exists\eta:Cy+D\eta\leq_{{\mathbf{K}}_{\cal Y}}e\\}$ $None$

Let us say that a convex-concave continuous function $\psi(x,y):{\cal
X}\times{\cal Y}\to{\mathbf{R}}$ is ${\cal K}$-representable on ${\cal
X}\times{\cal Y}$, if it admits representation of the form

$\forall(x\in{\cal X},y\in{\cal
Y}):\psi(x,y)=\inf\limits_{f,t,u}\left\\{f^{T}y+t:Pf+tp+Qu+Rx\leq_{\mathbf{K}}s\right\\}$
(3)

where ${\mathbf{K}}\in{\cal K}$. We call representation (3) essentially
strictly feasible, if the conic constraint

$Pf+tp+Qu\leq_{\mathbf{K}}s-Rx$

in variables $f,t,u$ is essentially strictly feasible for every $x\in{\cal
X}$.

###  3.2 Main observation

Assume that ${\cal Y}$ is compact and is given by essentially strictly
feasible ${\cal K}$-representation

${\cal Y}=\\{y:\exists\eta:Cy+D\eta\leq_{{\mathbf{K}}_{\cal Y}}e\\}.$ (4)

Then problem $(P)$ can be processed as follows: for $x\in{\cal X}$ we have

$\begin{array}[]{rl}\overline{\Psi}(x)=&\max\limits_{y\in{\cal
Y}}\inf\limits_{f,t,u}\left[f^{T}y+t:Pf+tp+Qu+Rx\leq_{\mathbf{K}}s\right]\\\
=&\inf\limits_{f,t,u}\left\\{\max\limits_{y\in{\cal
Y}}[f^{T}y+t]:Pf+tp+Qu+Rx\leq_{\mathbf{K}}s\right\\}\quad\left[\hbox{\begin{tabular}[]{l}Sion-
Kakutani Theorem; recall\\\ that ${\cal Y}$ is convex and compact\\\
\end{tabular}}\right]\\\
=&\inf\limits_{f,t,u}\left\\{\max\limits_{y,\eta}\left[f^{T}y:Cy+D\eta\leq_{{\mathbf{K}}_{\cal
Y}}e\right]+t:Pf+tp+Qu+Rx\leq_{\mathbf{K}}s\right\\}\\\
=&\inf\limits_{f,t,u}\left[\min\limits_{\lambda}\left[\lambda^{T}e:C^{T}\lambda=f,D^{T}\lambda=0,\lambda\geq_{{\mathbf{K}}_{\cal
Y}^{*}}0\right]+t:Pf+tp+Qu+Rx\leq_{\mathbf{K}}s\right\\}\\\
&\lx@intercol\hfil\left[\hbox{\begin{tabular}[]{l}by strong conic duality,
see, e.g., \cite[cite]{[\@@bibref{}{LMCOLN}{}{}, Theorem 1.4.4]};\\\ recall
that (\ref{eq16}) is essentially strictly
feasible,\end{tabular}}\right]\lx@intercol\\\ \end{array}$

so that the problem of interest

$\min_{x\in{\cal X}}\overline{\Psi}(x)$ $None$

reduces to the explicit ${\cal K}$-conic problem

$\min\limits_{x,\xi,f,t,u,\lambda}\left\\{e^{T}\lambda+t:\begin{array}[]{l}Pf+tp+Qu+Rx\leq_{\mathbf{K}}s,\\\
C^{T}\lambda=f,D^{T}\lambda=0,\lambda\geq_{{\mathbf{K}}_{\cal Y}^{*}}0,\\\
Ax+B\xi\leq_{{\mathbf{K}}_{\cal X}}c\\\ \end{array}\right\\}.$ $None$

Here,“reduction” means that the $x$-component of a feasible solution
$\zeta=(x,\xi,f,t,u,\lambda)$ to $(b)$ is a feasible solution to $(a)$ with
the value of the objective of the latter problem at $x$ being $\leq$ the value
of the objective of $(b)$ at $\zeta$, and the optimal values in $(a)$ and
$(b)$ are the same. Thus, as far as building feasible approximate solutions of
a prescribed accuracy $\epsilon>0$ in terms of the objective are concerned,
problem $(a)$ reduces to the explicit conic problem $(b)$. Note, however, that
$(a)$ and $(b)$ are not “exactly the same”—it may happen that $(a)$ is
solvable while $(b)$ is not so. “For all practical purposes,” this subtle
difference is of no importance since in actual computations exactly optimal
solutions usually are not reachable anyway.

##### Discussion.

Note that for continuous convex-concave function $\psi:{\cal X}\times{\cal
Y}\to{\mathbf{R}}$ the set

${\cal Z}=\\{[f;t;x]:x\in{\cal X},f^{T}y+t\geq{\psi}(x,y)\,\forall y\in{\cal
Y}\\}$

clearly is convex, and by the standard Fenchel duality we have

$\forall(x\in{\cal X},y\in{\cal
Y}):\psi(x,y)=\inf\limits_{f,t}\left[f^{T}y+t:[f;t;x]\in{\cal Z}\right].$ (5)

${\cal K}$-representability of $\psi$ on ${\cal X}\times{\cal Y}$ means that
(5) is preserved when replacing the set ${\cal Z}$ with its properly selected
${\cal K}$-representable subset. Given that ${\cal Z}$ is convex, this
assumption seems to be not too restrictive; taken together with ${\cal
K}$-representability of ${\cal X}$ and ${\cal Y}$, it can be treated as the
definition of ${\cal K}$-representability of the convex-concave function
$\psi$. The above derivation shows that convex-concave saddle point problem
with ${\cal K}$-representable domain and cost function (more precisely, the
primal minimization problem $(P)$ induced by this saddle point problem) can be
represented in explicit ${\cal K}$-conic form, at least when the ${\cal
K}$-representations of the cost and of (compact) ${\cal Y}$ are essentially
strictly feasible.

Note also that if ${\cal X}$ and ${\cal Y}$ are convex sets and a function
$\psi(x,y):{\cal X}\times{\cal Y}\to{\mathbf{R}}$ admits representation (3),
then $\psi$ automatically is convex in $x\in{\cal X}$ and concave in
$y\in{\cal Y}$.

###  3.3 Symmetry

Assume that representation (3) is essentially strictly feasible. Then for all
$x\in{\cal X},y\in{\cal Y}$ we have by conic duality

$\begin{array}[]{rcl}\psi(x,y)&=&\inf\limits_{f,t,u}\left\\{f^{T}y+t:Pf+tp+Qu+Rx\leq_{\mathbf{K}}s\right\\}\\\
&=&\sup\limits_{\overline{u}\in{\mathbf{K}}^{*}}\left\\{\overline{u}^{T}[Rx-s]:P^{T}\overline{u}+y=0,p^{T}\overline{u}+1=0,Q^{T}\overline{u}=0\right\\},\\\
\end{array}$

whence, setting

$\overline{{\cal X}}={\cal Y},\overline{{\cal Y}}={\cal
X},\overline{x}=y,\overline{y}=x,\overline{\psi}(\overline{x},\overline{y})=-\psi(\overline{y},\overline{x})=-\psi(x,y),$

we have

$\begin{array}[]{rcl}\lx@intercol(\forall\overline{x}\in\overline{{\cal
X}},\overline{y}\in\overline{{\cal Y}}):\hfil\lx@intercol\\\
\overline{\psi}(\overline{x},\overline{y})&=&-\psi(x,y)=\inf\limits_{\overline{u}\in{\mathbf{K}}^{*}}\left\\{-\overline{u}^{T}[Rx-s]:P^{T}\overline{u}+y=0,p^{T}\overline{u}+1=0,Q^{T}\overline{u}=0\right\\}\\\
&=&\inf\limits_{\overline{f},\overline{t},\overline{u}}\bigg{\\{}\overline{f}^{T}\overline{y}+\overline{t}:\underbrace{\left[\begin{array}[]{l}\overline{f}=-R^{T}\overline{u},\overline{t}=s^{T}\overline{u},Q^{T}\overline{u}=0,\\\
p^{T}\overline{u}+1=0,P^{T}\overline{u}+\overline{x}=0,\overline{u}\in{\mathbf{K}}^{*}\\\
\end{array}\right]}_{\Leftrightarrow\overline{P}\,\overline{f}+\overline{t}\overline{p}+\overline{Q}\overline{u}+\overline{R}\overline{x}\leq_{\overline{{\mathbf{K}}}}\overline{s}}\bigg{\\}}\\\
\end{array}$

with $\overline{{\mathbf{K}}}\in{\cal K}$. We see that a (essentially strictly
feasible) ${\cal K}$-representation of convex-concave function $\psi$ on
${\cal X}\times{\cal Y}$ induces straightforwardly a ${\cal K}$-representation
of the “symmetric entity”—the convex-concave function
$\overline{\psi}(y,x)=-\psi(x,y)$ on ${\cal Y}\times{\cal X}$, with immediate
consequences for converting the optimization problem

$\sup\limits_{y\in{\cal Y}}\left[\underline{\Psi}(y):=\inf\limits_{x\in{\cal
X}}\psi(x,y)\right]$ $None$

into the standard conic form.

###  3.4 Calculus of conic representations of convex-concave functions

Representations of the form (3) admit a calculus.

####  3.4.1 Raw materials

Raw materials for the calculus are given by

  1. 1.

Functions $\psi(x,y)=a(x)$, where $a(x)$, ${\mathop{\hbox{\rm
Dom}\,}}\,a\supset{\cal X}$, is ${\cal K}$-representable:

$t\geq a(x)\Leftrightarrow\exists
u:\overline{R}x+t\overline{p}+\overline{Q}u\leq_{\overline{{\mathbf{K}}}}\overline{s}$

In this case

$\psi(x,y)=\inf\limits_{f,t,u}\bigg{\\{}f^{T}y+t:\underbrace{f=0,\;\overline{R}x+t\overline{p}+\overline{Q}u\leq_{\overline{{\mathbf{K}}}}\overline{s}}_{\Leftrightarrow
Pf+tp+Qu+Rx\leq_{{\mathbf{K}}}s\hbox{\tiny\ with ${\mathbf{K}}\in{\cal
K}$}}\bigg{\\}}.$

  2. 2.

Functions $\psi(x,y)=-b(y)$, where $b(y)$, ${\mathop{\hbox{\rm
Dom}\,}}\,b\supset{\cal Y}$, is ${\cal K}$-representable:

$t\geq b(y)\Leftrightarrow\exists
u:\overline{R}y+t\overline{p}+\overline{Q}u\leq_{\overline{{\mathbf{K}}}}\overline{s}$

with essentially strictly feasible ${\cal K}$-representation. In this case

$\begin{array}[]{rcl}\psi(x,y)&=&-b(y)=-\inf\limits_{t,u}\left\\{t:\overline{R}y+t\overline{p}+\overline{Q}u\leq_{\overline{{\mathbf{K}}}}\overline{s}\right\\}\\\
&=&-\sup\limits_{u\in\overline{{\mathbf{K}}}^{*}}\left\\{-[\overline{R}^{T}u]^{T}y-s^{T}u:-u^{T}\overline{p}=1,\overline{Q}^{T}u=0\right\\}\hbox{\
[by conic duality]}\\\
&=&\inf\limits_{f,t,u}\bigg{\\{}f^{T}y+t:\underbrace{f=R^{T}u,t=s^{T}u,\overline{p}^{T}u+1=0,\overline{Q}^{T}u=0,u\geq_{\overline{{\mathbf{K}}}^{*}}0}_{\Leftrightarrow
Pf+tp+Qu\leq_{{\mathbf{K}}}s\hbox{\tiny\ with ${\mathbf{K}}\in{\cal
K}$}}\bigg{\\}}.\end{array}$

  3. 3.

Bilinear functions:

$\psi(x,y)\equiv
a^{T}x+b^{T}y+x^{T}Ay+c\Rightarrow\psi(x,y)=\min\limits_{f,t}\bigg{\\{}f^{T}y+t:\underbrace{f=A^{T}x+b,t=a^{T}x+c}_{\Leftrightarrow
Pf+tp+Rx\leq s}\bigg{\\}}.$

  4. 4.

“Generalized bilinear functions.” Let ${\mathbf{U}}\in{\cal K}$ and $E$ be the
embedding Euclidean space of ${\mathbf{U}}$.

    1. (a)

Let $\overline{{\cal X}}$ be a nonempty ${\cal K}$-representable set, and let
continuous mapping $F(x):{\overline{\cal X}}\to E$ possess ${\cal
K}$-representable ${\mathbf{U}}$-epigraph444This implies, in particular that
the ${\mathbf{U}}$-epigraph of $F$ is convex, or, which is the same, that $F$
is ${\mathbf{U}}$-convex:
$\forall(x^{\prime};x^{\prime\prime}\in\overline{{\cal
X}},\lambda\in[0,1]):F(\lambda
x^{\prime}+(1-\lambda)x^{\prime\prime})\leq_{{\mathbf{U}}}\lambda
F(x^{\prime})+(1-\lambda)F(x^{\prime\prime}).$

$\hbox{\rm Epi}_{{\mathbf{U}}}F:=\\{(x,z)\in\overline{{\cal X}}\times
E,z\geq_{{\mathbf{U}}}F(x)\\}=\\{(x,z):\exists
u:\overline{R}x+\overline{S}z+\overline{T}u\leq_{\overline{{\mathbf{K}}}}\overline{s}\\}.$

Then the function

$\overline{\psi}(x,y)=y^{T}F(x):\overline{{\cal
X}}\times{\mathbf{U}}^{*}\to{\mathbf{R}}$

is ${\cal K}$-representable on $\overline{{\cal X}}\times{\mathbf{U}}^{*}$:

$\begin{array}[]{rcl}\lx@intercol\forall(x\in\overline{{\cal
X}},y\in{\mathbf{U}}^{*}):\hfil\lx@intercol\\\
\overline{\psi}(x,y)&=&y^{T}F(x)=\inf\limits_{f}\left\\{f^{T}y:f\geq_{{\mathbf{U}}}F(x)\right\\}\\\
&=&\begin{array}[]{c}\inf\limits_{f,u}\left\\{f^{T}y:\overline{R}x+\overline{S}z+\overline{T}u\leq_{\overline{{\mathbf{K}}}}\overline{s}\right\\}.\end{array}\end{array}$

    2. (b)

Let ${\cal Y}$ be a nonempty ${\cal K}$-representable set, and let continuous
mapping $G(y):{\cal Y}\to E$ possess ${\cal K}$-representable
${\mathbf{U}}^{*}$-hypograph,

$\begin{array}[]{rcl}\hbox{\rm Hypo}_{{\mathbf{U}}^{*}}G&:=&\\{(y,w)\in{\cal
Y}\times E:w\leq_{{\mathbf{U}}^{*}}G(y)\\}\\\ &=&\\{(y,w):\exists
u:\underline{R}y+\underline{S}w+\underline{Q}u\geq_{\underline{{\mathbf{K}}}}\underline{s}\\}\qquad[\underline{{\mathbf{K}}}\in{\cal
K}],\end{array}$

the representation being essentially strictly feasible. Then the function

$\underline{\psi}(\underline{x},y)=\underline{x}^{T}G(y):{\mathbf{U}}\times{\cal
Y}\to{\mathbf{R}}$

is ${\cal K}$-representable on ${\mathbf{U}}\times{\cal Y}$:

$\begin{array}[]{rcl}\lx@intercol\forall(\underline{x}\in{\mathbf{U}},y\in{\cal
Y}):\hfil\lx@intercol\\\
\underline{\psi}(\underline{x},y)&=&\underline{x}^{T}G(y)=\sup\limits_{w}\left\\{\underline{x}^{T}w:w\leq_{{\mathbf{U}}^{*}}G(y)\right\\}\hbox{\
[due to $\underline{x}\in{\mathbf{U}}$]}\\\
&=&\sup\limits_{w,u}\left\\{\underline{x}^{T}w:\underline{R}y+\underline{S}w+\underline{Q}u\geq_{\underline{{\mathbf{K}}}}\underline{s}\right\\}\\\
&=&\inf_{\lambda}\left\\{[\underline{s}-\underline{R}y]^{T}\lambda:\underline{S}^{T}\lambda=\underline{x},\underline{Q}^{T}\lambda=0,\lambda\in\underline{{\mathbf{K}}}^{*}\right\\}\hbox{\
[by conic duality]}\\\
&=&\inf_{f,t,u=[\lambda;w]}\bigg{\\{}f^{T}y+t:\underbrace{\left[\begin{array}[]{l}f+\underline{R}^{T}\lambda=0,\underline{s}^{T}\lambda=t,\\\
\underline{S}^{T}\lambda=\underline{x},\underline{Q}^{T}\lambda=0,\lambda\in\underline{{\mathbf{K}}}^{*}\\\
\end{array}\right]}_{\Leftrightarrow
Pf+tp+Qu+R\underline{x}\leq_{{\mathbf{K}}}s}\bigg{\\}}\quad[{\mathbf{K}}\in{\cal
K}].\end{array}$ (6)

    3. (c)

Let ${\cal Y}$ and $G(\cdot)$ be as in item 4b) with $G({\cal
Y})\subset{\mathbf{U}}^{*}$, let ${\cal X}$ be a nonempty ${\cal
K}$-representable set, and let

$F(x):{\cal X}\to{\mathbf{U}}$

be continuous ${\mathbf{U}}$-convex mapping with ${\cal K}$-representable
${\mathbf{U}}$-epigraph:

$\begin{array}[]{rcl}\hbox{\rm Epi}_{\mathbf{U}}F&:=&\\{(x,z):x\in{\cal
X},z\geq_{{\mathbf{U}}}F(x)\\}\\\ &=&\\{x,z:\exists
v:\widehat{R}x+\widehat{S}z+\widehat{Q}v\leq_{\widehat{{\mathbf{K}}}}\widehat{s}\\}\qquad[\widehat{{\mathbf{K}}}\in{\cal
K}]\\\ \end{array}$ (7)

Then the function

$\psi(x,y)=F^{T}(x)G(y):{\cal X}\times{\cal Y}\to{\mathbf{R}}$

is continuous convex-concave and admits ${\cal K}$-representation as follows:

$\begin{array}[]{rcl}\lx@intercol\forall({x}\in{\cal X},y\in{\cal
Y}):\hfil\lx@intercol\\\ \psi(x,y)&=&F^{T}(x)G(y)\\\
&=&\inf\limits_{z}\left\\{z^{T}G(y):z\geq_{\mathbf{U}}F(x)\right\\}\hbox{\
[since $G(y)\in{\mathbf{U}}^{*}$]}\\\
&=&\inf\limits_{z,v}\left\\{z^{T}G(y):\widehat{R}x+\widehat{S}z+\widehat{Q}v\leq_{\widehat{{\mathbf{K}}}}\widehat{s}\right\\}\hbox{\
[by (\ref{today1})]}\\\
&=&\inf\limits_{z,v}\left\\{\inf\limits_{f,t}\left\\{f^{T}y+t:Pf+tp+Qu+Rz\leq_{{\mathbf{K}}}s\right\\}:\widehat{R}x+\widehat{S}z+\widehat{Q}v\leq_{\widehat{{\mathbf{K}}}}\widehat{s}\right\\}\end{array}$

due to (6)—note that on the domain on which $\inf_{z,v}$ is taken we have
$z\geq_{{\mathbf{U}}}F(x)\in{\mathbf{U}}$, making (6) applicable. We conclude
that

$\psi(x,y)=\inf\limits_{f,t,u=[z;v]}\bigg{\\{}f^{T}y+t:\underbrace{\left[\begin{array}[]{l}Pf+tp+Qu+Rz\leq_{{\mathbf{K}}}s,\\\
\widehat{R}x+\widehat{S}z+\widehat{Q}v\leq_{\widehat{{\mathbf{K}}}}\widehat{s}\\\
\end{array}\right]}_{\Leftrightarrow\widetilde{P}f+t\widetilde{p}+\widetilde{Q}u+\widetilde{R}x\leq_{\widetilde{{\mathbf{K}}}}\widetilde{c}}\bigg{\\}}\\\
\quad[\widetilde{{\mathbf{K}}}\in{\cal K}].$

####  3.4.2 Basic calculus rules

Basic calculus rules are as follows.

  1. 1.

[Direct summation] Let $\theta_{i}>0$, $i\leq I$, and let

$\begin{array}[]{c}\lx@intercol\forall(x^{i}\in{\cal X}^{i},y^{i}\in{\cal
Y}^{i},i\leq I):\hfil\lx@intercol\\\
\psi_{i}(x^{i},y^{i})=\inf\limits_{f_{i},t_{i},u_{i}}\left\\{f_{i}^{T}y^{i}+t_{i}:P_{i}f_{i}+t_{i}p_{i}+Q_{i}u_{i}+R_{i}x^{i}\leq_{{\mathbf{K}}_{i}}s_{i}\right\\}\\\
\end{array}.$

Then

$\begin{array}[]{rcl}\lx@intercol\forall\big{(}x=[x^{1};...;x^{I}]\in{\cal
X}={\cal X}_{1}\times...\times{\cal X}_{I},y=[y^{1};...;y^{I}]\in{\cal
Y}={\cal Y}_{1}\times...\times{\cal Y}_{I}\big{)}:\hfil\lx@intercol\\\
\psi(x,y)&:=&\sum\limits_{i}\theta_{i}\psi_{i}(x^{i},y^{i})\\\
&=&\inf\limits_{f,t,u=\\{f_{i},t_{i},u_{i},i\leq
I\\}}\bigg{\\{}f^{T}y+t:\underbrace{\begin{array}[]{l}f=[\theta_{1}f_{1};...;\theta_{I}f_{I}],t=\sum_{i}\theta_{i}t_{i},\\\
P_{i}f_{i}+t_{i}p_{i}+Q_{i}u_{i}+R_{i}x^{i}\leq_{{\mathbf{K}}_{i}}s_{i},\,1\leq
i\leq I\\\ \end{array}}_{\Leftrightarrow
Pf+tp+Qu+Rx\leq_{{\mathbf{K}}}s\hbox{\tiny\ with ${\mathbf{K}}\in{\cal
K}$}}\bigg{\\}}\\\ \end{array}$

  2. 2.

[Affine substitution of variables] Let

$\begin{array}[]{c}\lx@intercol\forall(\xi\in{\cal X}^{+},\eta\in{\cal
Y}^{+}):\hfil\lx@intercol\\\
{\psi_{+}}(\xi,\eta)=\inf\limits_{f_{+},t_{+},u_{+}}\left\\{f_{+}^{T}\eta+t_{+}:P_{+}f_{+}+t_{+}p_{+}+Q_{+}u_{+}+R_{+}\xi\leq_{{\mathbf{K}}_{+}}s_{+}\right\\}\\\
\end{array},$

and

$x\mapsto Ax+b:{\cal X}\to{\cal X}^{+},y\mapsto By+c:{\cal Y}\to{\cal Y}^{+}.$

Then

$\begin{array}[]{rcl}\lx@intercol\forall(x\in{\cal X},y\in{\cal
Y}):\hfil\lx@intercol\\\ \psi(x,y)&:=&{\psi_{+}}(Ax+b,By+c)\\\
&=&\inf\limits_{f_{+},t_{+},u_{+}}\left\\{f_{+}^{T}(By+c)+t_{+}:P_{+}f_{+}+t_{+}p_{+}+Q_{+}u_{+}+R_{+}[Ax+b]\leq_{{\mathbf{K}}_{+}}s_{+}\right\\}\\\
&=&\inf\limits_{f,t,u=[f_{+};t_{+};u_{+}]}\bigg{\\{}f^{T}y+t:\underbrace{\left[\begin{array}[]{l}f=B^{T}f_{+},t=t_{+}+f_{+}^{T}c\\\
P_{+}f_{+}+t_{+}p_{+}+Q_{+}u_{+}+R_{+}Ax\leq_{{\mathbf{K}}_{+}}s_{+}-R_{+}b\\\
\end{array}\right]}_{\Leftrightarrow Pf+tp+Qu+Rx\leq_{\mathbf{K}}s\hbox{
\small with ${\mathbf{K}}\in{\cal K}$}}\bigg{\\}}.\end{array}$

  3. 3.

[Taking conic combinations] This rule, evident by itself, is a combination of
the two preceding rules:
Let $\theta_{i}>0$ and $\psi_{i}(x,y):{\cal X}\times{\cal Y}\to{\mathbf{R}}$,
$i\leq I$, be such that

$\begin{array}[]{c}\lx@intercol\forall(x\in{\cal X},y\in{\cal
Y}):\hfil\lx@intercol\\\
\psi_{i}(x,y)=\inf\limits_{f_{i},t_{i},u_{i}}\left\\{f_{i}^{T}y^{i}+t_{i}:P_{i}f_{i}+t_{i}p_{i}+Q_{i}u_{i}+R_{i}x^{i}\leq_{{\mathbf{K}}_{i}}s_{i}\right\\}\\\
\end{array}.$

Then

$\begin{array}[]{rcl}\lx@intercol\forall(x\in{\cal X},y\in{\cal
Y}):\hfil\lx@intercol\\\
\psi(x,y)&:=&\sum\limits_{i}\theta_{i}\psi_{i}(x,y)\\\
&=&\inf\limits_{f,t,u=\\{f_{i},t_{i},u_{i},i\leq
I\\}}\bigg{\\{}f^{T}y+t:\underbrace{\left[\begin{array}[]{l}f=\sum_{i}\theta_{i}f_{i},t=\sum_{i}\theta_{i}t_{i},\\\
P_{i}f_{i}+t_{i}p_{i}+Q_{i}u_{i}+R_{i}x^{i}\leq_{{\mathbf{K}}_{i}}s_{i},\,1\leq
i\leq I\\\ \end{array}\right]}_{\Leftrightarrow
Pf+tp+Qu+Rx\leq_{{\mathbf{K}}}s\hbox{\small\, with ${\mathbf{K}}\in{\cal
K}$}}\bigg{\\}}.\end{array}$

  4. 4.

[Projective transformation in $x$-variable] Let

$\forall(x\in{\cal X},y\in{\cal
Y}):\psi(x,y)=\inf\limits_{f,t,u}\left\\{f^{T}y+t:Pf+tp+Qu+R{x}\leq_{{\mathbf{K}}}s\right\\}.$

Then

$\begin{array}[]{c}\lx@intercol(\forall(\alpha,x):\alpha>0,\alpha^{-1}x\in{\cal
X},\forall y\in{\cal Y})\hfil\lx@intercol\\\
\overline{\psi}((\alpha,x),y):=\alpha\psi(\alpha^{-1}x,y)=\inf\limits_{f,t,u}\bigg{\\{}f^{T}y+t:Pf+tp+Qu+Rx-\alpha
s\leq_{{\mathbf{K}}}0\bigg{\\}}.\\\ \end{array}$

  5. 5.

[Superposition in $x$-variable] Let ${\cal X}$, ${\cal Y}$ be ${\cal
K}$-representable, $\overline{{\cal X}}$ be a ${\cal K}$-representable subset
of some ${\mathbf{R}}^{n}$, and let ${\cal K}\ni{\mathbf{U}}$ be a cone in
${\mathbf{R}}^{n}$. Furthermore, assume that

$\overline{\psi}(\overline{x},y):\overline{{\cal X}}\times{\cal
Y}\to{\mathbf{R}}$

is a continuous convex-concave function which is ${\mathbf{U}}$-nondecreasing
in $\overline{x}\in\overline{{\cal X}}$, i.e.

$\forall(y\in{\cal
Y},\overline{x}^{\prime},\overline{x}^{\prime\prime}\in\overline{{\cal
X}}:\overline{x}^{\prime}\leq_{{\mathbf{U}}}\overline{x}^{\prime\prime}):\overline{\psi}(\overline{x}^{\prime\prime},y)\geq\overline{\psi}(\overline{x}^{\prime},y),$

and admits ${\cal K}$-representation on $\overline{{\cal X}}\times{\cal Y}$:

$\forall(\overline{x}\in\overline{{\cal X}},y\in{\cal
Y}):\,\overline{\psi}(\overline{x},y)=\inf\limits_{{f},{t},\overline{u}}\left\\{{f}^{T}y+{t}:\overline{P}{f}+{t}\overline{p}+\overline{Q}\overline{u}+\overline{R}\overline{x}\leq_{\overline{{\mathbf{K}}}}\overline{s}\right\\}.$

Let also

$x\mapsto X(x):{\cal X}\mapsto\overline{{\cal X}}$

be a ${\mathbf{U}}$-convex mapping such that the intersection of the
${\mathbf{U}}$-epigraph of the mapping with ${\cal X}\times\overline{{\cal
X}}$ admits ${\cal K}$-representation:

$\\{(x,\overline{x}):x\in{\cal X},\overline{x}\in\overline{{\cal
X}},\overline{x}\geq_{{\mathbf{U}}}X(x)\\}=\\{(x,\overline{x}):\exists
v:Ax+B\overline{x}+Cv\leq_{\widehat{{\mathbf{K}}}}d\\}.$

Then the function $\psi(x,y)=\overline{\psi}(X(x),y)$ admits ${\cal
K}$-representation on ${\cal X}\times{\cal Y}$:

$\begin{array}[]{rcl}\lx@intercol\forall(x\in{\cal X},y\in{\cal
Y}):\hfil\lx@intercol\\\
\psi(x,y)&=&\overline{\psi}(X(x),y)=\inf\limits_{\overline{x}}\\{\overline{\psi}(\overline{x},y):\overline{x}\in\overline{{\cal
X}}\ \&\ \overline{x}\geq_{{\mathbf{U}}}X(x)\\}\\\
&=&\inf\limits_{{f},{t},\overline{u},\overline{x}}\left\\{{f}^{T}y+{t}:\begin{array}[]{l}\overline{x}\in\overline{{\cal
X}},\overline{x}\geq_{{\mathbf{U}}}X(x)\\\
\overline{P}{f}+{t}\overline{p}+\overline{Q}\overline{u}+\overline{R}\overline{x}\leq_{\overline{{\mathbf{K}}}}\overline{s}\\\
\end{array}\right\\}\\\
&=&\inf\limits_{{f},{t},\overline{u},\overline{x},v}\left\\{{f}^{T}y+{t}:\begin{array}[]{l}Ax+B\overline{x}+Cv\leq_{\widehat{{\mathbf{K}}}}d\\\
\overline{P}{f}+{t}\overline{p}+\overline{Q}\overline{u}+\overline{R}\overline{x}\leq_{\overline{{\mathbf{K}}}}\overline{s}\\\
\end{array}\right\\}\\\
&=&\inf\limits_{{f},{t},u=[\overline{u},\overline{x},v]}\bigg{\\{}{f}^{T}y+{t}:\underbrace{\left[\begin{array}[]{l}Ax+B\overline{x}+Cv\leq_{\widehat{{\mathbf{K}}}}d\\\
\overline{P}{f}+{t}\overline{p}+\overline{Q}\overline{u}+\overline{R}\overline{x}\leq_{\overline{{\mathbf{K}}}}\overline{s}\\\
\end{array}\right]}_{\Leftrightarrow
Pf+tp+Qu+Rx\leq_{{\mathbf{K}}}s\hbox{\small\ with ${\mathbf{K}}\in{\cal
K}$}}\bigg{\\}}.\end{array}$

  6. 6.

[Partial maximization] Let

$\begin{array}[]{l}\forall(x\in{\cal X},y=[w;z]\in{\cal Y}):\\\
\psi(x,[w;z])=\inf\limits_{[g;h],\tau,u}\left\\{g^{T}w+h^{T}z+\tau:Gg+Hh+\tau
p+Qu+R{x}\leq_{{\mathbf{K}}}s\right\\}\qquad[{\mathbf{K}}\in{\cal
K}],\end{array}$

and let ${\cal Y}$ be compact and given by ${\cal K}$-representation:

${\cal Y}=\\{[w;z]:\exists v:Aw+Bz+Cv\leq_{{\mathbf{L}}}r\\}$

such that the conic constraint $Bz+Cv\leq_{{\mathbf{L}}}r-Aw$ in variables
$z,v$ is essentially strictly feasible for every $w\in{\cal W}=\\{w:\exists
z:[w;z]\in{\cal Y}\\}$. Then the function

$\overline{\psi}(x;w):=\max\limits_{z}\left\\{\psi(x,[w;z]):[w;z]\in{\cal
Y}\right\\}:{\cal X}\times{\cal W}\to{\mathbf{R}}$

is ${\cal K}$-representable provided it is continuous:555Representation to
follow holds true without the latter assumption; we make it to stay consistent
with our general definition of representability, where the convex-concave
function in question is assumed to be continuous.

$\begin{array}[]{l}{\forall(x\in{\cal X},w\in{\cal W}):}\\\
\overline{\psi}(x;w)=\max\limits_{z}\Big{\\{}\inf\limits_{[g;h],\tau,u}\left[g^{T}w+h^{T}z+\tau:Gg+Hh+\tau
p+Qu+R{x}\leq_{{\mathbf{K}}}s\right]:[w;z]\in{\cal Y}\Big{\\}}\\\
=\inf\limits_{[g;h],\tau,u}\Big{\\{}\max\limits_{z}\left[g^{T}w+h^{T}z+\tau:[w;z]\in{\cal
Y}\right]:Gg+Hh+\tau p+Qu+R{x}\leq_{{\mathbf{K}}}s\Big{\\}}\\\ \qquad\hbox{[by
the Sion-Kakutani Theorem; note that for $w\in{\cal W}$}\\\ \qquad\hbox{the
set $\\{z:[w;z]\in{\cal Y}\\}$ is nonempty, convex and compact]}\\\
=\inf\limits_{[g;h],\tau,u}\Big{\\{}\max\limits_{z,v}\left[g^{T}w+h^{T}z+\tau:Bz+Cv\leq_{{\mathbf{L}}}r-Aw\right]:\;{Gg+Hh+\tau
p+Qu+R{x}\leq_{{\mathbf{K}}}s\Big{\\}}}\\\
=\inf\limits_{[g;h],\tau,u}\Big{\\{}\min\limits_{\xi}\left[g^{T}w+(r-Aw)^{T}\xi+\tau:B^{T}\xi=h,C^{T}\xi=0,\xi\geq_{{\mathbf{L}}^{*}}0\right]:\\\
\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad{Gg+Hh+\tau
p+Qu+R{x}\leq_{{\mathbf{K}}}s\Big{\\}}}\qquad\hbox{\ [by conic duality]}\\\
=\inf\limits_{f,t,\overline{u}=[g,h,\tau,u,\xi]}\bigg{\\{}f^{T}w+t:\underbrace{\left[\begin{array}[]{l}f=g-A^{T}\xi,t=r^{T}\xi+\tau,\;B^{T}\xi=h,\;c^{T}\xi=0\\\
\xi\geq_{{\mathbf{L}}^{*}}0,Gg+Hh+\tau
p+Qu+R{x}\leq_{{\mathbf{K}}}s\end{array}\right]}_{\Leftrightarrow\overline{P}f+t\overline{p}+\overline{Q}\overline{u}+\overline{R}x\leq_{\overline{{\mathbf{K}}}}\overline{s}\
\hbox{with $\overline{{\mathbf{K}}}\in{\cal K}$}}\bigg{\\}}.\end{array}$

Note that the last three rules combine with symmetry to induce “symmetric”
rules on perspective transformation and superposition in $y$-variable and
partial minimization in $x$-variable.

  7. 7.

[Taking Fenchel conjugate] Let ${\cal X}\subset{\mathbf{R}}^{n}$, ${\cal
Y}\subset{\mathbf{R}}^{m}$ be nonempty convex compact sets given by
essentially strictly feasible ${\cal K}$-representations

${\cal X}=\\{x:\exists\xi:Ax+B\xi\leq_{{\mathbf{K}}_{\cal X}}c\\},\,{\cal
Y}=\\{y:\exists\eta:Cy+D\eta\leq_{{\mathbf{K}}_{\cal Y}}e\\},$

and assume that the conic constraint

$D^{T}\lambda=0\ \&\ \lambda\geq_{{\mathbf{K}}_{\cal Y}^{*}}0$

is essentially strictly feasible (this definitely is the case when
${\mathbf{K}}_{\cal Y}$ is polyhedral). Let, next, $\psi(x,y):{\cal
X}\times{\cal Y}\to{\mathbf{R}}$ be continuous convex-concave function given
by essentially strictly feasible ${\cal K}$-representation:

$\psi(x,y)=\inf\limits_{f,t,u}\left\\{f^{T}y+t:Pf+t\Pi+Qu+Rx\leq_{{\mathbf{K}}}s\right\\}.$

Consider the Fenchel conjugate of $\psi$—the function

$\psi_{*}(p,q)=\max\limits_{x\in{\cal X}}\min\limits_{y\in{\cal
Y}}\left[p^{T}x+q^{T}y-\psi(x,y)\right]:{\mathbf{R}}^{n}\times{\mathbf{R}}^{m}\to{\mathbf{R}}.$

We claim that $\psi_{*}$ is a continuous convex-concave ${\cal
K}$-representable function with ${\cal K}$-representation readily given by the
${\cal K}$-representations of ${\cal X}$, ${\cal Y}$, $\psi$

The fact that $\psi_{*}$ is well defined and continuous is readily given by
compactness of ${\cal X}$, ${\cal Y}$ and continuity of $\psi$. These
properties of the data imply by the Sion-Kakutani Theorem that

$\psi_{*}(p,q)=\min\limits_{y\in{\cal Y}}\max\limits_{x\in{\cal
X}}\left[p^{T}x+q^{T}y-\psi(x,y)\right].$

From the initial $\max\limits_{x}\min\limits_{y}$ definition of $\psi_{*}$ it
follows that

$\psi_{*}(p,q)=\max\limits_{x\in{\cal X}}\bigg{[}p^{T}x+\min\limits_{y\in{\cal
Y}}[q^{T}y-\psi(x,y)]\bigg{]}$

is the pointwise maximum of a family of affine functions of $p$ and thus is
convex in $p$. From the $\min\limits_{y}\max\limits_{x}$ representation of
$\psi_{*}$ it follows that

$\psi_{*}(p,q)=\min\limits_{y\in{\cal Y}}\big{[}q^{T}y+\max\limits_{x\in{\cal
X}}[p^{T}x-\psi(x,y)]\big{]}$

is the pointwise minimum of a family of affine functions of $q$ and thus is
concave in $q$.

It remains to build ${\cal K}$-representation of $\psi_{*}$. We have

$\displaystyle\psi_{*}(p,q)=\max\limits_{x\in{\cal X}}\min\limits_{y\in{\cal
Y}}\left[p^{T}x+q^{T}y-\psi(x,y)\right]$ (10) $\displaystyle=$
$\displaystyle\max\limits_{x\in{\cal X}}\bigg{[}p^{T}x+\min\limits_{y\in{\cal
Y}}\sup\limits_{f,t,u}\left\\{[q-f]^{T}y-t:Pf+t\Pi+Qu+Rx\leq_{{\mathbf{K}}}s\right\\}\bigg{]}$
$\displaystyle=$ $\displaystyle\max\limits_{x\in{\cal
X}}\bigg{[}p^{T}x+\sup\limits_{f,t,u}\bigg{\\{}\min\limits_{y\in{\cal
Y}}\\{[q-f]^{T}y\\}-t:Pf+t\Pi+Qu+Rx\leq_{{\mathbf{K}}}s\bigg{\\}}\bigg{]}$ [by
the Sion-Kakutani Theorem; recall that ${\cal Y}$ is convex and compact and
$[q-f]^{T}y-t$ is concave in $f,t,u$ and convex in $y$] $\displaystyle=$
$\displaystyle\max\limits_{x\in{\cal
X}}\bigg{[}p^{T}x+\sup\limits_{f,t,u}\bigg{\\{}\sup\limits_{\lambda}\left\\{-e^{T}\lambda:f-C^{T}\lambda=q,D^{T}\lambda=0,\lambda\geq_{{\mathbf{K}}_{\cal
Y}^{*}}0\right\\}-t:$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad{Pf+t\Pi+Qu+Rx\leq_{{\mathbf{K}}}s\bigg{\\}}\bigg{]}}$
[by Conic Duality; note that ${\cal Y}$ is given by essentially strictly
feasible ${\cal K}$-representation] $\displaystyle=$
$\displaystyle\sup\limits_{x\in{\cal
X},f,t,u,\lambda}\left\\{p^{T}x-t-e^{T}\lambda:\begin{array}[]{l}D^{T}\lambda=0,\;f-C^{T}\lambda=q,\lambda\geq_{{\mathbf{K}}_{\cal
Y}^{*}}0\\\ Pf+t\Pi+Qu+Rx\leq_{{\mathbf{K}}}s\end{array}\right\\}$
$\displaystyle=$
$\displaystyle\sup\limits_{x,\xi,f,t,u,\lambda}\left\\{p^{T}x-t-e^{T}\lambda:\begin{array}[]{ll}D^{T}\lambda=0&(a)\\\
f-C^{T}\lambda=q&(b)\\\ \lambda\geq_{{\mathbf{K}}_{\cal Y}^{*}}0&(c)\\\
Pf+t\Pi+Qu+Rx\leq_{{\mathbf{K}}}s&(d)\\\ Ax+B\xi\leq_{{\mathbf{K}}_{\cal
X}}c&(e)\\\ \end{array}\right\\}$ (16)

Now, the ${\cal K}$-representation of ${\cal X}$ is essentially strictly
feasible, so that $(e)$ admits an essentially strictly feasible solution
$\bar{x},\bar{\xi}$; observe that $\bar{x}\in{\cal X}$. The ${\cal
K}$-representation of $\psi$ is essentially strictly feasible, implying that
$\bar{x}$ can be augmented by $\bar{f}$, $\bar{t}$, $\bar{u}$ in such a way
that $(\bar{x},\bar{f},\bar{t},\bar{u})$ is an essentially strictly feasible
solution to $(d)$. By the origin of constraints $(a)$—$(c)$, their system is
feasible for all $f,q$ as a system of constraints on $\lambda$, . Besides
this, by assumption, there exists a representation ${\mathbf{K}}_{\cal
Y}^{*}=M\times N$ with regular cone $M$ and polyhedral cone $N$ and
$\lambda^{\prime}\in[\hbox{\rm int}M]\times N$ such that
$D^{T}\lambda^{\prime}=0$. Taking into account that the system $(a)$—$(c)$,
considered as a system in variable $\lambda$, is solvable for all $f,q$, there
exists $\lambda^{\prime\prime}\in{\mathbf{K}}_{{\cal Y}^{*}}$ such that
$D^{T}\lambda^{\prime\prime}=0$ and
$\bar{f}-C^{T}\lambda^{\prime\prime}=q+C^{T}\lambda^{\prime}$. This implies
that $\bar{\lambda}=\lambda^{\prime}+\lambda^{\prime\prime}$ taken together
with $\bar{f}$ is an essentially strictly feasible solution to the system
$(a)$—$(c)$ of constraints in variables $\lambda$ and $f$. The bottom line is
that the constraints $(a)$—$(e)$ in variables $x,\xi,f,t,u,\lambda$ form an
essentially strictly feasible conic constraint. Besides this, problem (16) is
bounded by its origin. By Conic Duality we conclude from (16) that

$\displaystyle\psi_{*}(p,q)$ $\displaystyle=$
$\displaystyle\min\limits_{\alpha,\beta,\gamma,\delta,\epsilon}\left\\{\beta^{T}q+s^{T}\delta+c^{T}\epsilon:\begin{array}[]{l}\gamma\geq_{{\mathbf{K}}_{\cal
Y}}0,\delta\geq_{{\mathbf{K}}^{*}}0,\epsilon\geq_{{\mathbf{K}}_{\cal
X}^{*}}0\\\ R^{T}\delta+A^{T}\epsilon=p,B^{T}\epsilon=0,P^{T}\delta+\beta=0\\\
\Pi^{T}\delta=-1,Q^{T}\delta=0,D\alpha-C\beta+e=\gamma\\\
\end{array}\right\\}$ $\displaystyle=$
$\displaystyle\min\limits_{\beta,\tau,w=(\alpha,\delta,\epsilon)}\left\\{\beta^{T}q+\tau:\begin{array}[]{l}\delta\geq_{{\mathbf{K}}^{*}}0,\epsilon\geq_{{\mathbf{K}}_{\cal
X}^{*}}0,\;\tau=s^{T}\delta+c^{T}\epsilon\\\
R^{T}\delta+A^{T}\epsilon=p,B^{T}\epsilon=0,P^{T}\delta+\beta=0\\\
\Pi^{T}\delta=-1,Q^{T}\delta=0,D\alpha-C\beta+e\geq_{{\mathbf{K}}_{\cal
Y}}0\\\ \end{array}\right\\}$

which is the desired ${\cal K}$-representation of $\psi_{*}$. $\square$

###  3.5 Illustrations

A. Our first illustration is motivated by a statistical application of saddle
point optimization—near-optimal recovery of linear forms in Discrete
observation scheme, see [10, Section 3.1]. Let

$\psi(x,y)=\ln\left(\sum_{i}{\hbox{\rm e}}^{x_{i}}y_{i}\right):{\cal
X}\times{\cal Y}\to{\mathbf{R}},$

${\cal X}$ and ${\cal Y}$ be ${\cal K}$-representable, and let ${\cal Y}$,
$0\not\in{\cal Y}$, be is a compact subset of the nonnegative orthant. Because
for $z>0$

$\ln z=\inf_{u}ze^{u}-u-1,$

for $y\geq 0$ we clearly have

$\begin{array}[]{c}\ln\left(\sum_{i}{\hbox{\rm
e}}^{x_{i}}y_{i}\right)=\inf\limits_{u}\left[\left(\sum_{i}{\hbox{\rm
e}}^{x_{i}}y_{i}\right){\hbox{\rm
e}}^{u}-u-1\right]=\inf\limits_{f,u}\left[\sum_{i}y_{i}f_{i}-u-1:f_{i}\geq{\hbox{\rm
e}}^{x_{i}+u}\right]\\\
=\inf\limits_{f,t,u}\left\\{f^{T}u+t:f_{i}\geq{\hbox{\rm
e}}^{x_{i}+u}\,\forall i\ \&\ t\geq-u-1\right\\}\end{array}$

The resulting representation is a ${\cal K}$-representation, provided that the
closed w.r.t. taking finite direct products and passing to the dual cone
family ${\cal K}$ of regular cones contains ${\mathbf{R}}_{+}$, the
exponential cone

${\mathbf{E}}{=}{\hbox{\rm cl}\,}\\{[t;s;r]:t\geq s{\hbox{\rm
e}}^{r/s},s>0\\},$

and, therefore, its dual cone

${\mathbf{E}}^{*}={\hbox{\rm
cl}\,}\\{[\tau;\sigma;-\rho]:\tau>0,\rho>0,\sigma\geq\rho\ln(\rho/\tau)-\rho\\}.$

B. Let now

$\psi(x,y)=\left(\sum_{i=1}^{n}\theta^{p}_{i}(x)y_{i}\right)^{1/p}$

where $p>1$, $\theta_{i}(x)$ are nonnegative ${\cal K}$-representable real-
valued functions on ${\cal K}$-representable set ${\cal X}$, and ${\cal Y}$ is
a ${\cal K}$-representable subset of the nonnegative orthant. In this case, as
is easily seen, for all $(x\in{\cal X},y\in{\cal Y})$ it holds

$\psi(x,y)=\inf\limits_{[f;t]}\left\\{f^{T}y+t:t\geq 0,f\geq 0,t^{{p-1\over
p}}f_{i}^{{1\over p}}\geq\kappa\theta_{i}(x),i\leq n\right\\}$ $None$

which can immediately be converted into ${\cal K}$-representation, provided
${\cal K}$ contains 3D Lorentz cone
${\mathbf{L}}^{3}=\\{x\in{\mathbf{R}}^{3}:x_{3}\geq\sqrt{x_{1}^{2}+x_{2}^{2}}\\}$
and $p$ is rational, see [4, Section 3.3] or [5, Section 2.3.5].
C. In our next example, ${\cal X}\subset{\mathbf{R}}^{m\times n}$ and ${\cal
Y}\subset{\mathbf{S}}^{m}_{+}$ are nonempty convex sets, and

$\psi(x,y)=2\sqrt{{\mathop{\hbox{\rm Tr}}}(x^{T}yx)}:{\cal X}\times{\cal
Y}\to{\mathbf{R}}.$

Taking into account that for $a\geq 0$ one has $2\sqrt{a}=\inf_{s>0}[a/s+s]$,
we have

$\begin{array}[]{rcl}\lx@intercol\forall(x\in{\cal X},y\in{\cal
Y}):\hfil\lx@intercol\\\ \psi(x,y)&=&2\sqrt{{\mathop{\hbox{\rm
Tr}}}(y[xx^{T}])}=\inf_{g}\left\\{2\sqrt{{\mathop{\hbox{\rm
Tr}}}(yg)}:g\succeq xx^{T}\right\\}\\\ &=&\inf_{f,s}\left\\{{\mathop{\hbox{\rm
Tr}}}(yf)+s:s>0,fs\succeq xx^{T}\right\\}\\\
&=&\inf\limits_{f,s}\left\\{{\mathop{\hbox{\rm
Tr}}}(yf)+s:\left[\begin{array}[]{c|c}f&x\cr\hline\cr
x^{T}&sI_{n}\cr\end{array}\right]\succeq 0\right\\}.\end{array}$

The resulting representation is ${\cal K}$-representation, provided that
${\cal K}$ contains semidefinite cones.

> This is how C works in Robust Markowitz Portfolio Selection (cf, e.g., [6,
> 8])
>
> $\min\limits_{x\in{\cal X}}\max_{y\in{\cal
> Y}}\left[-r^{T}x+2\rho\sqrt{x^{T}yx}\right]$ $None$
>
> (here $x\in{\mathbf{R}}^{n}$ is the composition of portfolio, $r$ is the
> vector of expected returns, and $y$ is the uncertain covariance matrix of
> the returns). Assuming for the sake of definiteness that ${\cal Y}$ is cut
> off ${\mathbf{S}}^{n}_{+}$ by the constraints
>
> $a_{i}^{T}ya_{i}+b_{i}y+yb_{i}^{T}\preceq p_{i},i\leq I,y_{-}\leq y\leq
> y_{+}$
>
> (where $\leq$ for matrices acts entrywise) and applying our machinery on the
> top of the above semidefinite representation of $2\sqrt{x^{T}yx}$, the
> saddle point problem reduces to
>
>
> $\begin{array}[]{l}\min\limits_{x,s,\alpha_{i},\mu_{\pm}}\bigg{\\{}-r^{T}x+\rho\left[s+\sum_{i}{\mathop{\hbox{\rm
> Tr}}}(\alpha_{i}p_{i})+{\mathop{\hbox{\rm
> Tr}}}(\mu_{+}y_{+}-\mu_{-}y_{-})\right]:\\\
><EMAIL_ADDRESS>> x^{T}&s\cr\end{array}\right]\succeq 0\\\ \alpha_{i}\succeq 0,i\leq
> I,\mu_{\pm}\geq 0,x\in{\cal X}\end{array}\right\\}.\lx@intercol\end{array}$

D. In our concluding example, ${\cal K}$ contains the products of semidefinite
cones, ${\cal X}={\mathbf{R}}^{m\times n}$, ${\cal Y}={\mathbf{S}}^{n}_{+}$,
and

$\psi(x,y)={\mathop{\hbox{\rm Tr}}}(x^{T}xy^{1/2}):{\cal X}\times{\cal
Y}\to{\mathbf{R}}.$

This is a “generalized bilinear function”; in terms of item 4.c of Section
3.4.1, we have $F(x)=x^{T}x$, $G(y)=y^{1/2}$,
${\mathbf{U}}={\mathbf{U}}^{*}={\mathbf{S}}^{n}_{+}$, and

$\begin{array}[]{rcl}{\hbox{\rm Epi}}_{\mathbf{U}}F&:=&\\{(x,z):z\succeq
x^{T}x\\}=\left\\{(x,z):\left[\begin{array}[]{c|c}z&x^{T}\cr\hline\cr
x&I_{m}\cr\end{array}\right]\succeq 0\right\\},\\\
\mathrm{Hypo}_{{\mathbf{U}}^{*}}G&:=&\\{(y,w):y\in{\mathbf{S}}^{n}_{+},w\preceq
y^{1/2}\\}=\left\\{(y,w):\exists v:\left[\begin{array}[]{c|c}y&v\cr\hline\cr
v&I_{n}\cr\end{array}\right]\succeq 0,v\succeq 0,w\preceq
v\right\\}.\end{array}$

With these data, the construction from item 4.c of Section 3.4.1 leads
straightforwardly to the following semidefinite representation of $\psi$:

$\forall(x\in{\mathbf{R}}^{m\times
n},y\in{\mathbf{S}}^{n}_{+}):\psi(x,y):={\mathop{\hbox{\rm
Tr}}}(x^{T}xy^{1/2})=\inf\limits_{f,t,u=(z,\beta,\gamma)}\left\\{{\mathop{\hbox{\rm
Tr}}}(fy)+t:\begin{array}[]{l}f\in{\mathbf{S}}^{n},\beta\in{\mathbf{R}}^{n\times
n},\gamma\in{\mathbf{S}}^{n},z\in{\mathbf{S}}^{n}\\\ t={\mathop{\hbox{\rm
Tr}}}(\gamma),z\preceq\beta+\beta^{T}\\\
\left[\begin{array}[]{c|c}f&\beta\cr\hline\cr\beta^{T}&\gamma\cr\end{array}\right]\succeq
0,\left[\begin{array}[]{c|c}z&x^{T}\cr\hline\cr
x&I_{m}\cr\end{array}\right]\succeq 0\\\ \end{array}\right\\}.$

##  4 Well-structured variational inequalities with monotone operators

###  4.1 Preliminaries

Let ${\cal X}$ be a nonempty convex subset of Euclidean space $E$. A vector
field $F(x):x\to E$ is called monotone, if

$\langle F(x)-F(y),x-y\rangle\geq 0\;\forall x,y\in{\cal X}.$

Variational Inequality ${\mathrm{VI}}(F,{\cal X})$ reads

$\hbox{Find\ }x_{*}\in{\cal X}:\langle F(y),{x_{*}}-y\rangle\leq 0\;\forall
y\in{\cal X}.$ $None$

Solutions which are sought in ${\mathrm{VI}}(F,{\cal X})$ are called weak
solutions; they do exist whenever ${\cal X}$ is a compact set and $F$ is
monotone on ${\cal X}$. Strong solutions are points $x_{*}\in{\cal X}$ such
that

$\langle F(x_{*}),x-x_{*}\rangle\geq 0\;\forall x\in{\cal X};$

from monotonicity of $F$ it follows that every strong solution is a weak one.
The opposite is true provided that $F$ is continuous on ${\cal X}$.

A natural (in)accuracy measure for a candidate approximate solution to
${\mathrm{VI}}(F,{\cal X})$ is the dual gap function

${\epsilon_{\hbox{\tiny\rm VI}}}[x|{\cal X}]=\sup_{y\in{\cal X}}\langle
F(y),x-y\rangle;$

this function is nonnegative and is zero exactly at weak solutions to
$VI(F,{\cal X})$.

Our current goal is to develop a framework for converting “well-structured”
VI’s with monotone vector fields into the usual conic problems, thus bringing
them within the grasp of Interior-Point polynomial time methods and software
like CVX. What follows can be seen as a streamlined “well-structured” (i.e.,
conic representation-oriented) extension of what in [13, Section 7.4] was
called a convex representation of a monotone operator.

###  4.2 Conic representability of monotone vector fields and monotone VI’s in
conic form

####  4.2.1 Conic representation of a monotone vector field

Let $F(x):{\cal X}\to{E}$ be a monotone and continuous vector field on
nonempty convex subset ${\cal X}$ of Euclidean space $E$. Consider the set

${\cal F}[F,{\cal X}]=\\{[t;g;x]\in{\mathbf{R}}\times E\times E:x\in{\cal
X},t-\langle g,y\rangle\geq\langle F(y),x-y\rangle\,\,\forall y\in{\cal X}\\}$
(19)

and let us make several straightforward observations.

4.2.1.A. ${\cal F}[F,{\cal X}]$ is a convex set which contains all triples
$[\langle{F(x)},x\rangle;F(x);x]$, $x\in{\cal X}$; this set is closed provided
${\cal X}$ is so. Besides this, ${\cal F}[F,{\cal X}]$ is $t$-monotone:

$[t;g;x]\in{\cal F}[F,{\cal X}]\;\mbox{and}\;t^{\prime}\geq
t\Rightarrow[t^{\prime};g;x]\in{\cal F}[F,{\cal X}].$

> Indeed, ${\cal F}[F,{\cal X}]$ is the intersection of solution set of the
> system of nonstrict linear constraints
>
> $t-\langle g,y\rangle-\langle F(y),x\rangle\geq-\langle
> F(y),y\rangle,\,y\in{\cal X}$
>
> in variables $g,t,x$ (this set is closed and convex) with the convex set
> $\\{[t;g;x]:x\in{\cal X}\\}$ (which is closed if so is ${\cal X}$). By
> monotonicity, for every $x\in{\cal X}$ we have
>
> $\langle F(x),x-y\rangle\geq\langle F(y),x-y\rangle\,\,\forall y\in{\cal
> X},$
>
> so that $[\langle F(x),x\rangle;F(x);x]\in{\cal F}[F,{\cal X}]$; and
> $t$-monotonicity is evident.

4.2.1.B. For $\epsilon\geq 0$, let

${\cal X}_{*}(\epsilon)=\\{[g;t]\in E\times{\mathbf{R}}:\sup\limits_{y\in{\cal
X}}[t-\langle g,y\rangle]\leq\epsilon\\},$ (20)

so that ${\cal X}_{*}(\epsilon)$ is a nonempty closed convex set. Then for
every $\epsilon\geq 0$, $\epsilon$-solutions to ${\mathrm{VI}}(F,{\cal
X})$—points $x\in{\cal X}$ such that

${\epsilon_{\hbox{\tiny\rm VI}}}[x|F]:=\sup\limits_{y\in{\cal X}}\langle
F(y),x-y\rangle\leq\epsilon$

are exactly the points

$x:\exists(t,g):[t;g;x]\in{\cal F}[F,{\cal X}]\ \;\mbox{and}\;\ [t;g]\in{\cal
X}_{*}(\epsilon);$ (21)

> Indeed, let $x,t,g$ be such that $[t;g;x]\in{\cal F}[F,{\cal X}]$ and
> $[t;g]\in{\cal X}_{*}(\epsilon)$. From the first inclusion it follows that
> $x\in{\cal X}$ and
>
> $t-\langle g,y\rangle\geq\langle F(y),x-y\rangle\,\,\forall y\in{\cal X},$
>
> while from the second inclusion it follows that $t-\langle
> g,y\rangle\leq\epsilon$ for all $y\in{\cal X}$. Taken together, these two
> relations imply that $x\in{\cal X}$ and $\langle
> F(y),x-y\rangle\leq\epsilon$ for all $y\in{\cal X}$, i.e.,
> ${\epsilon_{\hbox{\tiny\rm VI}}}(x|F)\leq\epsilon$. Vice versa, if
> $x\in{\cal X}$, $\epsilon\geq 0$, and ${\epsilon_{\hbox{\tiny\rm
> VI}}}[x|F]\leq\epsilon$, then the triple $t=\epsilon,g=0,x$ clearly belongs
> to ${\cal F}[F,{\cal X}]$ and $[t;g]\in{\cal X}_{*}(\epsilon)$.

#####  ${\cal K}$-representation of $(F,{\cal X})$.

Given a continuous monotone vector field $F:{\cal X}\to E$ on a nonempty
convex subset ${\cal X}$ of Euclidean space $E$, let us call a conic
constraint666Recall that we have fixed a family ${\cal K}$ of regular cones in
Euclidean spaces, and by our standing convention, all cones to be considered
below belong to ${\cal K}$.

$Xx+Gg+tT+Uu\leq_{{\mathbf{K}}}a$ (22)

in variables $t\in{\mathbf{R}}$, $g\in E$, $x\in E$, and
$u\in{\mathbf{R}}^{k}$ a ${\cal K}$-representation of $(F,{\cal X})$, if the
set

${\cal T}:=\\{[t;g;x]:\exists u:Xx+Gg+tT+Uu\leq_{{\mathbf{K}}}a\\}$ (23)

possesses the following two properties:

  * (i)

${\cal T}$ is contained in ${\cal F}[F,{\cal X}]$ and, along with the latter
set, is “$t$-monotone:”

$[t;g;x]\in{\cal T}\ \;\mbox{and}\;\ t^{\prime}\geq
t\Rightarrow[t^{\prime};g;x]\in{\cal T}$

(note that when ${\cal T}\neq\emptyset$, $t$-monotonicity is equivalent to
${T}\leq_{{\mathbf{K}}}0$);

and

  * (ii)

${\cal T}$ contains the set

$\\{[\langle F(x),x\rangle;F(x);x],x\in{\cal X}\\}$ $None$

If the set (23) satisfies (i) and the relaxed version of (ii), specifically,

  * (ii’)

${\cal T}$ contains the set

$\\{[t;F(x);x]:t>\langle F(x),x\rangle,x\in{\cal X}\\}$ $None$

we say that (22) is an almost ${\cal K}$-representation of $(F,{\cal X})$.

Let us make an immediate observation:

###### Remark 4.1

In the situation described in the beginning of this section, let ${\cal X}$ be
closed, and let ${\cal Y}$ be a convex set such that

$\hbox{\rm Conv}\\{[x^{T}F(x);F(x);x],x\in{\cal X}\\}\subset{\cal
Y}\subset{\hbox{\rm cl}\,}\hbox{\rm Conv}\\{[x^{T}F(x);F(x);x],x\in{\cal
X}\\}$

Then every ${\cal K}$-representation of ${\cal Y}$ represents $(F,{\cal X})$.

####  4.2.2 Conic form of conic-representable monotone VI

Our main observation is as follows:

###### Proposition 4.1

Let ${\cal X}\subset E$ be nonempty convex compact given by essentially
strictly feasible ${\cal K}$-representation:

${\cal X}=\\{x:\exists
v:Ax+Bv\leq_{{\mathbf{L}}}b\\},\qquad\qquad{[{\mathbf{L}}\in{\cal K}],}$ (24)

so that ${\cal X}_{*}(\epsilon)$, see (20), by conic quality, admits ${\cal
K}$-representation as follows:

${\cal
X}_{*}(\epsilon)=\\{[t;g]:\exists\lambda:A^{T}\lambda+g=0,B^{T}\lambda=0,t+b^{T}\lambda\leq\epsilon,\lambda\geq_{{\mathbf{L}}^{*}}0\\}.$
(25)

Let, moreover, $F:{\cal X}\to E$ be a continuous monotone vector field, and
let (22) be an almost ${\cal K}$-representation of $(F,{\cal X})$. Then for
every $\epsilon>0$ the system of conic constraints

$\begin{array}[]{rcll}Xx+Gg+tT+Uu&\leq_{{\mathbf{K}}}&a&(a)\\\
A^{T}\lambda+g&=&0&(b.1)\\\ B^{T}\lambda&=&0&(b.2)\\\
t+b^{T}\lambda&\leq&\epsilon&(b.3)\\\
\lambda&\geq_{{\mathbf{L}}^{*}}&0&(b.4)\\\ \end{array}$ (26)

in variables $x,g,t,u,$ and $\lambda$ is feasible, and $x$-component of any
feasible solution belongs to ${\cal X}$ and is an $\epsilon$-solution to
${\mathrm{VI}}(F,{\cal X})$:

${\epsilon_{\hbox{\tiny\rm VI}}}[x|F]\leq\epsilon.$

Therefore, finding an $\epsilon$-solution to ${\mathrm{VI}}(F,{\cal X})$
reduces to finding a feasible solution to an explicit ${\cal K}$-conic
constraint.

When (22) is a ${\cal K}$-representation of $(F,{\cal X})$, the above
conclusion holds true for all $\epsilon\geq 0$.

Proof. Let us fix $\epsilon>0$, and let $\bar{x}$ solve ${\mathrm{VI}}(F,X)$
(a solution exists since ${\cal X}$ is compact). Then $\langle
F(\bar{x}),\bar{x}-y\rangle\leq 0$ for all $y\in{\cal X}$ due to continuity of
$F$ on ${\cal X}$. Consequently, given $\epsilon>0$, setting $\bar{t}=\langle
F(\bar{x}),\bar{x}\rangle$, $\bar{g}=F(\bar{x})$, we have
$[\bar{t}+\epsilon;\bar{g};\bar{x}]\in{\cal X}_{*}(\epsilon)$, implying by
(25) that there exists $\bar{\lambda}$ such that $t=\bar{t}+\epsilon$,
$g=\bar{g}$, $\lambda=\bar{\lambda}$ solve (26.$b$.1-4). Besides this, by
(ii’) there exists $\bar{u}$ such that $x=\bar{x}$, $g=\bar{g}$,
$t=\bar{t}+\epsilon$, $u=\bar{u}$ solve (26.$a$). Thus, (26) is feasible.

Next, if $x,g,t,u,\lambda$ is a feasible solution to (26), then by (26.$a$)
one has $[t;g;x]\in{\cal T}$, with ${\cal T}$ given by (23), whence
$[t;g;x]\in{\cal F}[F,{\cal X}]$, implying that $x\in{\cal X}$, see (19).
Besides this, (26.$b$.1-4) say that $[t;g]\in{\cal X}_{*}(\epsilon)$. Thus,
$[t;g;x]\in{\cal F}[F,{\cal X}]$ and $[t;g]\in{\cal X}_{*}(\epsilon)$,
implying by 4.2.1.B that ${\epsilon_{\hbox{\tiny\rm VI}}}[x|F]\leq\epsilon$.

Finally, when (22) is a ${\cal K}$-representation of $(F,{\cal X})$, the above
reasoning works for $\epsilon=0$. $\square$

###  4.3 Calculus of conic representations of monotone vector fields

${\cal K}$-representations of pairs $(F,{\cal X})$ (${\cal X}$ is a nonempty
convex subset of Euclidean space $E$, $F:{\cal X}\to E$ is a continuous
monotone vector field) admit a calculus; for verification of claims to follow,
see Appendix A.

####  4.3.1 Raw materials

Raw materials for the calculus of ${\cal K}$-representable monotone vector
fields include:

  1. 1.

[Affine monotone vector field] Let ${\cal K}$ contain all Lorentz cones. Then
affine monotone vector field $F(x)=Ax+a$ on ${\cal X}=E={\mathbf{R}}^{n}$ is
${\cal K}$-represented by conic constraint (cf. [13, Proposition 7.4.3])

$t\geq x^{T}\bar{A}x+a^{T}x,g=Ax+a$ (27)

in variables $t,g,x$, where $\bar{A}={1\over 2}[A+A^{T}]$.

  2. 2.

[Gradient field of continuously differentiable ${\cal K}$-representable convex
function] Let ${\cal X}$ be nonempty convex compact set, and $f(x):{\cal
X}\to{\mathbf{R}}$ be continuously differentiable convex function with ${\cal
K}$-representable epigraph,

$\\{(x,s):s\geq f(x),x\in{\cal X}\\}=\\{(x,s):\exists
u:Ax+sp+Qu\leq_{{\mathbf{K}}}a\\},$ (28)

the representation being essentially strictly feasible. Then the conic
constraint

$t\geq s+r,Ax+sp+Qu\leq_{{\mathbf{K}}}a,r\geq
a^{T}\lambda,A^{T}\lambda=g,p^{T}\lambda=-1,Q^{T}\lambda=0,\lambda\geq_{{\mathbf{K}}^{*}}0$
(29)

in variables $t,g,x,s,r,\lambda,$ and $u$ represents
$(F(\cdot):=f^{\prime}(\cdot),{\cal X})$ (cf. [13, Proposition 7.4.4]).

  3. 3.

[Monotone vector field associated with continuously differentiable ${\cal
K}$-representable convex-concave function $\psi$] Let ${\cal K}$ contain the
3D Lorentz cone, and let ${\cal U}\subset{\mathbf{R}}^{n_{u}}$ and ${\cal
V}\subset{\mathbf{R}}^{n_{v}}$ be ${\cal K}$-representable nonempty compact
sets:

$\begin{array}[]{rclr}{\cal
U}&=&\\{u:\exists\alpha:\,Au+B\alpha\leq_{{\mathbf{K}}}a\\},&\qquad(a)\\\
{\cal V}&=&\\{v:\exists\beta:\,Cv+D\beta\leq_{{\mathbf{L}}}b\\},&(b)\\\
\end{array}$ (30)

both representations being essentially strictly feasible. Assume that
$\psi(u,v):{\cal U}\times{\cal V}\mapsto{\mathbf{R}}$ is a continuously
differentiable convex-concave function which is ${\cal K}$-representable on
${\cal U}\times{\cal V}$ with essentially strictly feasible representation
(see Section 3.1); that is, $\psi$ admits representation

$\forall(u\in{\cal U},v\in{\cal
V}):\psi(u,v)=\inf\limits_{f,\tau,\xi}\left\\{f^{T}v+\tau:Pf+\tau
p+Q\xi+Ru\leq_{{\mathbf{M}}}c\right\\}$ (31)

such that the conic constraint $Pf+\tau p+Q\xi\leq_{{\mathbf{M}}}c-Ru$ in
variables $f,\tau,\xi$ is essentially strictly feasible for every $u\in{\cal
U}$. Let

$F(u,v)=[\nabla_{u}\psi(u,v);-\nabla_{v}\psi(u,v)]:{\cal X}:={\cal
U}\times{\cal V}\to E:={\mathbf{R}}^{n_{u}}\times{\mathbf{R}}^{n_{v}}$

be the vector field associated with ${\cal U},{\cal V},\psi$; it is well known
that this field is monotone. Then

$(i)$ The set

${\cal Z}=\left\\{(t\in{\mathbf{R}},g=[h;e]\in E,x=[u;v]\in{\cal X}):\exists
r,s:\begin{array}[]{ll}r>\max\limits_{\zeta\in{\cal
V}}\left[\zeta^{T}e+\psi(u,\zeta)\right]&(a)\\\ s>\max\limits_{\omega\in{\cal
U}}\left[\omega^{T}h-\psi(\omega,v)\right]&(b)\\\ t\geq r+s&(c)\\\
\end{array}\right\\}$ (32)

satisfies the relations

$\begin{array}[]{rclr}{\cal Z}&\subset&{\cal F}[F,{\cal X}]&\qquad(a)\\\
x\in{\cal X},g=F(x),t>x^{T}F(x)&\Rightarrow&[t;g;x]\in{\cal Z}.&(b)\\\
\end{array}$ (33)

$(ii)$ Besides this, ${\cal Z}$ is nothing but the projection on the plane of
$(t,g=[h;e],x=[u;v])$-variables of the solution set of the conic constraint

$\left[\begin{array}[]{l}t\geq
r+s,\;r\geq\theta+\gamma^{T}b{+\tau},\;s\geq\theta^{\prime}+c^{T}\delta+a^{T}\epsilon,\\\
Au+B\alpha\leq_{{\mathbf{K}}}a,\;Cv+D\beta\leq_{{\mathbf{L}}}b,\;Pf+\tau
p+Q\xi+Ru\leq_{{\mathbf{M}}}c\\\
C^{T}\gamma=f+e,D^{T}\gamma=0,\;P^{T}\delta+v=0,\;p^{T}\delta=-1,\;Q^{T}\delta=0,\;R^{T}\delta+A^{T}\epsilon=h,\;B^{T}\epsilon=0,\\\
\gamma\geq_{{\mathbf{L}}^{*}}0,\;\delta\geq_{{\mathbf{M}}^{*}}0,\;\epsilon\geq_{{\mathbf{K}}^{*}}0,\;\eta\geq
0,\theta\geq 0,\;\eta\theta\geq 1,\;\eta^{\prime}\geq 0,\;\theta^{\prime}\geq
0,\;\eta^{\prime}\theta^{\prime}\geq 1\end{array}\right]$ (34)

in variables
$t,g=[h;e],x=[u;v],r,s,f,\tau,\xi,\alpha,\beta,\gamma,\eta,\theta,\delta,\epsilon,\eta^{\prime},$
and $\theta^{\prime}$.777When one of the authors was a freshman at Math.
Department of Moscow State University, his mate left lecture on Linear Algebra
writing in his notebook: “The lecture was terminated due to shortage of
indices.” The list of variables in (34) comes close to this natural limit…

Taken together, $(i)$ and $(ii)$ say that the conic constraint (34) almost
represents $(F,{\cal X})$.

  4. 4.

[Univariate monotone rational vector field] Let ${\cal
X}=[a,b]\subset{\mathbf{R}}$ ($-\infty<a<b<\infty$), and let $\alpha(x)$ and
$\beta(x)$ be real algebraic polynomials such that $\beta(x)>0$ on ${\cal X}$.
Suppose that the univariate vector field given on ${\cal X}$ by the function
$F(x)={\alpha(x)\over\beta(x)}$ is nondecreasing on ${\cal X}$, and that
${\cal K}$ contain all semidefinite cones. Then the set

${\cal Y}:=\hbox{\rm Conv}\\{[xF(x);F(x);x],x\in{\cal X}\\}$

admits explicit ${\cal K}$-representation which, by Remark 4.1, represents
$(F,{\cal X})$.

####  4.3.2 Calculus rules

Calculus rules are as follows.

  1. 1.

[Restriction on a ${\cal K}$-representable set] Let conic constraint

$Xx+Gg+tT+Uu\leq_{{\mathbf{K}}}a$ (35)

in variables $t,g,x,u$ represent (almost represent) $(F,{\cal X})$, and let
set ${\cal Y}\subset E$ be ${\cal K}$-representable:

${\cal Y}=\\{y\in E:\exists v:Ay+Bv\leq_{{\mathbf{L}}}b\\}$ (36)

and have a nonempty intersection ${\cal Z}={\cal Y}\cap{\cal X}$ with ${\cal
X}$. Denoting by $\bar{F}$ the restriction of $F$ on ${\cal Z}$, the conic
constraint

$\\{Xx+Gg+tT+Uu\leq_{{\mathbf{K}}}a,\,Ax+Bv\leq_{{\mathbf{L}}}b\\}$ (37)

in variables $t,g,x,u,v$ represents (resp., almost represent) $(\bar{F},{\cal
Z})$ (cf. [13, Proposition 7.4.5]).

  2. 2.

[Direct summation] For $k\leq K$, let ${\cal X}_{k}$ be nonempty convex
subsets of Euclidean spaces $E_{k}$ and $F_{k}:{\cal X}_{k}\to E_{k}$ be
continuous monotone vector fields, and let

$X_{k}x+G_{k}g_{k}+t_{k}T_{k}+U_{k}u_{k}\leq_{{\mathbf{K}}_{k}}a_{k},\;1\leq
k\leq K$ (38)

be ${\cal K}$-representations of $(F_{k},{\cal X}_{k})$. Denote

$F([x_{1};...;x_{K}])=[F_{1}(x_{1});...;F_{K}(x_{K})]\;\;\mbox{and}\;\;{\cal
X}={\cal X}_{1}\times...\times{\cal X}_{K}.$

Then the conic constraint

$\begin{array}[]{rcll}X_{k}x_{k}+G_{k}g_{k}+t_{k}T_{k}+U_{k}u_{k}&\leq_{{\mathbf{K}}_{k}}&a_{k},k\leq
K&(a)\\\ t&=&\sum_{k}t_{k}&(b)\\\ \end{array}$ (39)

in variables $t$, $g:=[g_{1};...;g_{K}]$, $x:=[x_{1};...;x_{K}]$,
$t_{1},...,t_{K}$, $u_{1},...,u_{K}$ ${\cal K}$-represents $(F,{\cal X})$.

When conic constraints (38) almost represent $(F_{k},{\cal X}_{k})$, (39)
almost represents $(F,{\cal X})$ (cf. [13, Proposition 7.4.6]).

  3. 3.

[Taking conic combinations] Let ${\cal X}$ be a nonempty convex subset of
Euclidean space $E$, and let $F_{1},...,F_{K}$ be continuous monotone vector
fields on $X$ with $(F_{k},{\cal X})$ admitting ${\cal K}$-representations

$X_{k}x+G_{k}g+tT_{k}+U_{k}u_{k}\leq_{{\mathbf{K}}_{k}}a_{k},\;1\leq k\leq K.$
(40)

Let, further, $\alpha_{k}>0$ be given, and let

$F(x)=\sum_{k}\alpha_{k}F_{k}(x):{\cal X}\to E.$

The conic constraint

$\begin{array}[]{lr}X_{k}x+G_{k}g_{k}+t_{k}T_{k}+U_{k}u_{k}\leq_{{\mathbf{K}}_{k}}a_{k},\;1\leq
k\leq K&\qquad(a)\\\ g=\sum_{k}\alpha_{k}g_{k}&(b)\\\
t=\sum_{k}\alpha_{k}t_{k}&(c)\\\ \end{array}$ (41)

in variables $t,g,x,\\{t_{k},g_{k},u_{k},k\leq K\\}$ is a ${\cal
K}$-representation of $(F,{\cal X})$.

When (40) are almost representations of $(F_{k},{\cal X})$, (41) is almost
representation of $(F,{\cal X})$.

  4. 4.

[Affine substitution of variables] Let ${\cal X}$ be a nonempty convex subset
of $E$, $F$ be a continuous monotone vector field on $X$, with $(F,{\cal X})$
given by ${\cal K}$-representation

$Xx+Gg+tT+Uu\leq_{{\mathbf{K}}}a.$ (42)

Assume that $\xi\mapsto A\xi+a$ is an affine mapping from Euclidean space
$\Lambda$ to $E$, and

$\Xi=\\{\xi:A\xi+a\in{\cal X}\\}.$

Then vector field $\Phi(\xi)=A^{T}F(A\xi+a)$: $\Xi\to\Lambda$ is continuous
and monotone, and the conic constraint

$\tau=t-\langle
g,a\rangle,\,\gamma=A^{T}g,\;X(A\xi+a)+Gg+tT+Uu\leq_{{\mathbf{K}}}a$ (43)

in variables $\tau,\gamma,\xi,g,t,$ and $u$ represents $(\Phi,\Xi)$.
When (42) nearly represents $(F,{\cal X})$, conic constraint (43) nearly
represents $(\Phi,\Xi)$.

###  4.4 Illustrations

####  4.4.1 “Academic” illustration

Let ${\cal K}$ contain Lorentz cones, $M\in{\mathbf{R}}^{n\times n}$ be such
that $\overline{M}={1\over 2}[M+M^{T}]\succeq 0$, and let ${\cal
X}\subset{\mathbf{R}}^{n}_{+}$ be nonempty and ${\cal K}$-representable:

${\cal X}=\\{x:\exists
u_{0}:A_{0}x+B_{0}u_{0}\leq_{{\mathbf{K}}_{0}}a_{0}\\}.$ (44)

Suppose that the operator

$F(x)=Mx-[f_{1}(x);...;f_{n}(x)]$ (45)

is monotone on ${\cal X}$, and that functions $f_{i}(x)$ and
$-\sum_{i}x_{i}f_{i}(x)$ are ${\cal K}$-representable on ${\cal X}$:

$\begin{array}[]{lr}\\{(x,s):x\in{\cal X},s\geq f_{i}(x)\\}=\\{(x,s):\exists
u_{1i}:A_{1i}x+sB_{1i}+C_{1i}u_{1i}\leq_{{\mathbf{K}}_{1i}}a_{1i}\\}&\qquad(a_{i})\\\
\\{(x,s):x\in{\cal X},s\geq-\sum_{i}x_{i}f_{i}(x)\\}=\\{(x,s):\exists
u_{2}:A_{2}x+sB_{2}+C_{2}u_{2}\leq_{{\mathbf{K}}_{2}}a_{2}\\}&(b)\\\
\end{array}$ (46)

Observe, that when $M\succeq\alpha I_{m}$ with $\alpha>0$, $F$ definitely is
monotone provided that $f(x):=[f_{1}(x);...;f_{n}(x)]$ is Lipschitz continuous
on ${\cal X}$ with Lipschitz constant w.r.t. $\|\cdot\|_{2}$ bounded with
$\alpha$.

Given $x\in{\cal X}$ and $g\in{\mathbf{R}}^{n}$, let us consider the function

$f_{x,g}(y)=g^{T}y+F^{T}(y)(x-y)=-y^{T}{\overline{M}}y+\sum_{i}\left[g_{i}y_{i}+x_{i}[[My]_{i}-f_{i}(y)]+y_{i}f_{i}(y)\right]:{\cal
X}\to{\mathbf{R}}.$

We are in the situation where $x_{i}\geq 0$ for $x\in{\cal X}$, so that

$\begin{array}[]{ll}&\\{(y,r):y\in{\cal X},f_{x,g}(y)\geq r\\}\\\
=&\left\\{(y,r):\exists
u_{0},{s_{0}},s_{1i},s_{2}:\,\begin{array}[]{l}A_{0}y+B_{0}u_{0}\leq_{{\mathbf{K}}_{0}}a_{0},\;y^{T}\overline{M}y-s_{0}\leq
0\\\ s_{1i}+f_{i}(y)\leq 0,\;1\leq i\leq n,s_{2}-\sum_{i}y_{i}f_{i}(y)\leq
0\\\ \sum_{i}[g_{i}+[M^{T}x]_{i}]y_{i}-{s_{0}}+\sum_{i}x_{i}s_{1i}+s_{2}\geq
r\end{array}\right\\}\\\ =&\bigg{\\{}(y,r):\exists
u_{0},{s_{0}},s_{1i},s_{2},u_{1i},u_{2}:\\\
&\lx@intercol\hfil\qquad\qquad\left.\begin{array}[]{l}A_{0}y+B_{0}u_{0}\leq_{{\mathbf{K}}_{0}}a_{0},\,y^{T}\overline{M}y-s_{0}\leq
0,\;A_{2}y-s_{2}B_{2}+C_{2}u_{2}\leq_{{\mathbf{K}}_{2}}a_{2}\\\
A_{1i}y-s_{1i}B_{1i}+C_{1i}u_{1i}\leq_{{\mathbf{K}}_{1i}}a_{1i},\;1\leq i\leq
n\\\ \sum_{i}[g_{i}+[M^{T}x]_{i}]y_{i}{-s_{0}}+\sum_{i}x_{i}s_{1i}+s_{2}\geq
r\end{array}\right\\}\lx@intercol\\\ \end{array}$

Taking into account that $\overline{M}\succeq 0$, the constraint
$y^{T}\overline{M}y-s_{0}\leq 0$ can be represented by strictly feasible conic
constraint

$A_{3}y+s_{0}B_{3}\leq_{{\mathbf{K}}_{3}}a_{3}$

on Lorentz cone ${{\mathbf{L}}^{3}}$, we get

$\displaystyle\max\limits_{y\in{\cal
X}}f_{x,g}(y)=\sup\limits_{y,u_{0},{s_{0},}s_{1i},s_{2},u_{1i},u_{2}}\bigg{\\{}\sum_{i}[g_{i}+[M^{T}x]_{i}]y_{i}{-s_{0}}+\sum_{i}x_{i}s_{1i}+s_{2}:$
(49)
$\displaystyle\left.\begin{array}[]{l}A_{0}y+B_{0}u_{0}\leq_{{\mathbf{K}}_{0}}a_{0},\,A_{3}y+s_{0}B_{3}\leq_{{\mathbf{K}}_{3}}a_{3}\\\
A_{1i}y-s_{1i}B_{1i}+C_{1i}u_{1i}\leq_{{\mathbf{K}}_{1i}}a_{1i},1\leq i\leq
n,\,A_{2}y-s_{2}B_{2}+C_{2}u_{2}\leq_{{\mathbf{K}}_{2i}}a_{2}\\\
\end{array}\right\\}.$

Assume that the system of conic constraints (49) in variables
$y,{s_{0},}u_{0},s_{1i},s_{2},u_{1i}$ and $u_{2}$ is essentially strictly
feasible. Then, by conic quality,

$\displaystyle\max\limits_{y\in{\cal X}}f_{x,g}(y)$ $\displaystyle=$
$\displaystyle\min_{\mu,\nu,\xi_{i},\eta}\bigg{\\{}a_{0}^{T}\mu+a_{3}^{T}\nu+\sum_{i}a_{1i}^{T}\xi_{i}+a_{2}^{T}\eta:$
$\displaystyle\qquad\left.\begin{array}[]{l}M^{T}x+g=A_{0}^{T}\mu+A_{3}^{T}\nu+\sum_{i}A_{1i}^{T}\xi_{i}+A_{2}^{T}\eta\\\
x_{i}+B_{1i}^{T}\xi_{i}=0,\,1\leq i\leq
n,\,B_{2}^{T}\eta=-1{,\,B_{3}^{T}\nu=-1}\\\
B_{0}^{T}\mu=0,C_{1i}^{T}\xi_{i}=0,\,1\leq i\leq n,\,C_{2}^{T}\eta=0,\\\
\mu\geq_{{\mathbf{K}}_{0}^{*}}0,\,\nu\geq_{{\mathbf{K}}_{3}^{*}}0,\,\xi_{i}\geq_{{\mathbf{K}}_{1i}^{*}}0,\,1\leq
i\leq n,\,\eta\geq_{{\mathbf{K}}_{2}^{*}}0\\\ \end{array}\right\\}.$

Now, recalling what $f_{x,g}(y)$ is, we end up with ${\cal K}$-representation
of ${\cal F}[F,{\cal X}]$:

$\begin{array}[]{rcl}{\cal F}[F,{\cal X}]&:=&\left\\{[t;g;x]:x\in{\cal
X},t-g^{T}y\geq F^{T}(y)[x-y]\,\,\forall y\in{\cal X}\right\\}\\\
&=&\bigg{\\{}[t;g;x]:\exists u_{0},\mu,\nu,\xi_{i},\eta:\\\
<EMAIL_ADDRESS>a_{0}^{T}\mu+a_{3}^{T}\nu+\sum_{i}a_{1i}^{T}\xi_{i}+a_{2}^{T}\eta,\,A_{0}x+B_{0}u_{0}\leq_{{\mathbf{K}}_{0}}a_{0}\\\
M^{T}x+g=A_{0}^{T}\mu+A_{3}^{T}\nu+\sum_{i}A_{1i}^{T}\xi_{i}+A_{2}^{T}\eta\\\
x_{i}+B_{1i}^{T}\xi_{i}=0,1\leq i\leq
n,\,B_{2}^{T}\eta=-1{,\,B_{3}^{T}\nu=-1}\\\
B_{0}^{T}\mu=0,C_{1i}^{T}\xi_{i}=0,1\leq i\leq n,\,C_{2}^{T}\eta=0\\\
\mu\geq_{{\mathbf{K}}_{0}^{*}}0,\nu\geq_{{\mathbf{K}}_{3}^{*}}0,\xi_{i}\geq_{{\mathbf{K}}_{1i}^{*}}0,1\leq
i\leq
n,\,\eta\geq_{{\mathbf{K}}_{2}^{*}}0\end{array}\right\\},\lx@intercol\end{array}$

so that the conic constraint

$\left[\begin{array}[]{l}t\geq
a_{0}^{T}\mu+a_{3}^{T}\nu+\sum_{i}a_{1i}^{T}\xi_{i}+a_{2}^{T}\eta,\,A_{0}x+B_{0}u_{0}\leq_{{\mathbf{K}}_{0}}a_{0}\\\
x_{i}+B_{1i}^{T}\xi_{i}=0,1\leq i\leq
n,\,B_{2}^{T}\eta=-1,{,\,B_{3}^{T}\nu=-1}\\\
B_{0}^{T}\mu=0,C_{1i}^{T}\xi_{i}=0,1\leq i\leq n,\,C_{2}^{T}\eta=0\\\
\mu\geq_{{\mathbf{K}}_{0}^{*}}0,\nu\geq_{{\mathbf{K}}_{3}^{*}}0,\xi_{i}\geq_{{\mathbf{K}}_{1i}^{*}}0,1\leq
i\leq n,\,\eta\geq_{{\mathbf{K}}_{2}^{*}}0\end{array}\right]$

in variables $t,g,x,u_{0},\mu,\nu,\xi_{i}$ and $\eta$ is a ${\cal
K}$-representation of $(F,{\cal X})$.

####  4.4.2 Nash Equilibrium

The “covering story” for this example is as follows:

> $n\geq 2$ retailers intend to enter certain market, say, one of red
> herrings. To this end they should select their “selling capacities” (say,
> rent areas at malls) $x_{i}$, $1\leq i\leq n$, in given ranges ${\cal
> X}_{i}=[0,X_{i}]$ ($0<X_{i}<\infty$). With the selections
> $x=[x_{1};...;x_{n}]\in{\cal X}={\cal X}_{1}\times...,\times{\cal
> X}_{n}\subset{\mathbf{R}}^{n}_{+}$, the monthly loss of the $i$-th retailer
> is
>
> $\phi_{i}(x)=c_{i}x_{i}-{x_{i}\over\sum_{j=1}^{K}x_{j}+a}b,$
>
> where $c_{i}x_{i}$, $c_{i}>0$, is the price of the capacity $x_{i}$, $b>0$
> is the dollar value of the demand on red herrings, and $a>0$ is the total
> selling capacity of the already existing retailers; the term
> $-{x_{i}\over\sum_{j=1}^{n}x_{j}+a}b$ is the minus the revenue of the $i$-th
> retailer under the assumption that the total demand is split between
> retailers proportionally to their selling capacities.
>
> We want to find is a Nash equilibrium – a point
> $x^{*}=[x^{*}_{1};...;x^{*}_{n}]\in{\cal X}$ such that every one of the
> functions
> $\phi_{i}(x_{i}^{*},...,x_{i-1}^{*},x_{i},x_{i+1}^{*},...,x_{n}^{*})$
> attains its minimum over $x_{i}\in{\cal X}_{i}$ at $x_{i}=x_{i}^{*}$, so
> that for the $i$-th retailer there is no incentive to deviate from capacity
> $x_{i}^{*}$ provided that all other retailers $j$ stick to capacities
> $x_{j}^{*}$, and this is so for all $i$.

As is immediately seen, the Nash Equilibrium problem in question is convex,
meaning that $\phi_{i}(x)$ are convex in $x_{i}$ and concave in
$x^{i}=(x_{i},...,x_{i-1},x_{i+1},...,x_{n})$ and, on the top of it,
$\sum_{i}\phi_{i}(x)$ is convex on ${\cal X}$. It is well known (for
justification, see, e.g., [14]) that for such a problem, the vector field

$F(x)=\left[{\partial\phi_{1}(x)\over\partial
x_{1}};{\partial\phi_{2}(x)\over\partial
x_{2}};...;{\partial\phi_{n}(x)\over\partial x_{n}}\right]:{\cal
X}\to{\mathbf{R}}^{n}$

is monotone, and that Nash Equilibria are exactly the weak$=$strong solutions
to ${\mathrm{VI}}(F,{\cal X})$. Specifying ${\cal K}$ as the family of direct
products of Lorentz cones, we are about to demonstrate that $F$ admits an
explicit ${\cal K}$-representation on ${\cal X}$, allowing to reduce the
problem of finding Nash Equilibrium to an explicit Second Order conic problem.
This is how the construction goes (to save notation, in what follows we set
${b}=a=1$, which always can be achieved by appropriate scaling of the
capacities and loss functions):

  1. 1.

Observe that all we need is a ${\cal K}$-representation ${\cal R}(t,g,x,u)$ of
$(F,{\cal X})$—a ${\cal K}$-conic constraint in variables $t\in{\mathbf{R}}$,
$g\in{\mathbf{R}}^{n}$, $x\in{\mathbf{R}}^{n}$ and additional variables
$u$—satisfying the requirements specified in Section 4.2.1. By Proposition
4.1, given ${\cal R}$, for $\epsilon\geq 0$ we can write down an explicit
${\cal K}$-conic constraint ${\cal C}_{\epsilon}(t,g,x,u,v)$ in variables
$t,g,x$ and additional variables $u,v$, with the size of the constraint
(dimension of the associated cone and the total number of variables)
independent of $\epsilon$ such that the constraint is feasible, and the
$x$-component of any feasible solution to the constraint is an
$\epsilon$-solution to ${\mathrm{VI}}(F,{\cal X})$:

$x\in{\cal X}\ \&\ {\epsilon_{\hbox{\tiny\rm VI}}}[x|F]=\max_{y\in{\cal
X}}F^{T}(y)[x-y]\leq\epsilon.$

As a result, finding $\epsilon$-solution to ${\mathrm{VI}}(F,{\cal X})$
reduces to solving an explicit solvable Second Order feasibility conic problem
of the size independent of $\epsilon$.

  2. 2.

Thus, all we need is to find an explicit ${\cal K}$-representation of
$(F,{\cal X})$. This can be done as follows:

    1. (a)

Consider the convex-concave function

$\psi(u,v)=-{u\over u+v+1}:{\mathbf{R}}^{2}_{+}\to{\mathbf{R}}$

along with the associated monotone vector field

$\Phi(u,v)=\left[{\partial\psi(u,v)\over\partial
u};-{\partial\psi(u,v)\over\partial
v}\right]=\left[-{v+1\over(u+v+1)^{2}};-{u\over(u+v+1)^{2}}\right].$

Let also $A_{i}$ be $2\times n$ matrix with $i$-th column $[1;0]$ and all
remaining columns equal to $[0;1]$, and let
$G(x)=\nabla\left({1\over\sum_{j}x_{j}+1}\right)$. As is immediately seen, we
have

$\forall
x\in{\mathbf{R}}^{n}_{+}:\Psi(x):=2c+\sum_{i=1}^{n}A_{i}^{T}\Phi(A_{i}x)+G(x)=2F(x),$

so that a ${\cal K}$-representation of $F$ is readily given by ${\cal
K}$-representations of the constant monotone vector field $\equiv c$, of
$\Phi$, and of $G$ via our calculus (rules on affine substitution of argument
and on summation).

A ${\cal K}$-representation of the constant vector field $\equiv c$ is
trivial; it is given by the system of linear equalities $t=c^{T}x,g=c$ on
variables
$(t,g,x)\in{\mathbf{R}}\times{\mathbf{R}}^{n}\times{\mathbf{R}}^{n}$. A ${\cal
K}$-representation of the gradient vector field $G(x)$ is given by calculus
rule 2 in Section 4.3.1; we are in the case where (28) reads

$\begin{array}[]{rcl}\\{(x,s):s\geq f(x),x\in X\\}&=&\bigg{\\{}(x,s):-x\leq
0,x\leq X:=[X_{1};...;X_{n}],\\\
&&\quad\underbrace{-\big{[}0;\hbox{\footnotesize$\sum$}_{i}x_{i}-s;\hbox{\footnotesize$\sum$}_{i}x_{i}+s\big{]}\leq_{{\mathbf{L}}^{3}}[2;1;1]}_{\hbox{\footnotesize$\begin{array}[]{ll}\Leftrightarrow&x+1+s\geq
0,\\\
&(\hbox{\footnotesize$\sum$}_{i}x_{i}+1+s)^{2}\geq(\hbox{\footnotesize$\sum$}_{i}x_{i}+1-s)^{2}+4\\\
\Leftrightarrow&s(\sum_{i}x_{i}+1)\geq 1\\\
\end{array}$}}\bigg{\\}},\end{array}$

so that (29), as seen from immediate computation, reduces to the system of
constraints

$\begin{array}[]{c}t\geq r+s,\,0\leq x\leq
X,\,r\geq\sum_{i}\max[X_{i}(g_{i}+\theta),0]+\theta-2\nu\\\
\underbrace{\big{[}2;\hbox{\footnotesize$\sum$}_{i}x_{i}+1-s;\hbox{\footnotesize$\sum$}_{i}x_{i}+1+s\big{]}\geq_{{\mathbf{L}}^{3}}0}_{\Leftrightarrow
s(\sum_{j}x_{j}+1)\geq
1},\,\underbrace{[2\nu;\theta-1;\theta+1]\geq_{{\mathbf{L}}^{3}}0}_{\Leftrightarrow\nu^{2}\leq\theta}\\\
\end{array}$

in variables $t,g,x,\theta,\nu$.

    2. (b)

It remains to find a ${\cal K}$-representation of the vector field $\Phi$ on a
rectangle $\Xi={\cal U}\times{\cal V}$, ${\cal U}=[0,U]$, ${\cal V}=[0,V]$
with given $U>0$, $V>0$ (they should be large enough in order for $A_{i}x$,
$x\in{\cal X}$, to take values in the rectangle).

Let us use the construction described in item 3 of Section 4.3.1. By (i) of
item 3, the set

$\overline{{\cal
Z}}=\left\\{(t\in{\mathbf{R}},g=[h;e]\in{\mathbf{R}}^{2},x=[u;v]\in\Xi):\exists
r,s:\begin{array}[]{ll}r\geq\max\limits_{\zeta\in{\cal V}}\left[\zeta
e+\psi(u,\zeta)\right]\\\ s\geq\max\limits_{\omega\in{\cal
U}}\left[\omega^{T}h-\psi(\omega,v)\right]\\\ t\geq r+s\\\
\end{array}\right\\}$

satisfies the relations

$\begin{array}[]{rcl}\overline{{\cal Z}}&\subset&{\cal F}[\Phi,\Xi]\\\
x\in{\cal X},g=\Phi(x),t\geq
x^{T}\Phi(x)&\Rightarrow&[t;g;x]\in\overline{{\cal Z}},\end{array}$

so that all we need to get a ${\cal K}$-representation of $\Phi$ is to
represent $\overline{{\cal Z}}$ as a projection onto the plane of
$t,g,x$-variables of the solution set of ${\cal K}$-conic constraint in
variables $t,g,x$ and additional variables. To this end note that for all
$(u,v)\in\Xi={\cal U}\times{\cal V}$ one has

${\psi(u,v)=\min\limits_{f,t,s,\tau}\left\\{\rule{0.0pt}{28.45274pt}\right.fv+t:\,\underbrace{\left[\begin{array}[]{l}\tau\geq
0,\,1\geq f\geq 0,\,s\geq 0,\,t\leq 1,\,s+\tau\leq 1\\\
{[2s;u-f;u+f]\in{\mathbf{L}}^{3}}\\\
{[2(1-s);t-f;t-f+2]\in{\mathbf{L}}^{3}}\\\
{[2;u-\tau+1;u+\tau+1]\in{\mathbf{L}}^{3}}\end{array}\right]}_{\Leftrightarrow\,(f,t,s,\tau)\in\Pi_{+}}\left.\rule{0.0pt}{28.45274pt}\right\\}}$
(51)

and

${-\psi(u,v)=\min\limits_{f,t,s}\left\\{\rule{0.0pt}{22.76228pt}\right.fu+t:\,\underbrace{\left[\begin{array}[]{l}1\geq
f\geq 0,\,0\leq s\leq 1,\,t\leq 1\\\ {[2s;v+1-f;v+1+f]\in{\mathbf{L}}^{3}}\\\
{[2(1-s);t-1;t+1]\in{\mathbf{L}}^{3}}\end{array}\right]}_{\Leftrightarrow\,(f,t,s)\in\Pi_{-}}\left.\rule{0.0pt}{22.76228pt}\right\\},}$
(52)

see Section B for justification. Since $\Pi_{\pm}$ are nonempty convex compact
sets, by the Sion-Kakutani Theorem one has from (51):

$\begin{array}[]{rcl}\max\limits_{\zeta\in{\cal V}}\left[\zeta
e+\psi(u,\zeta)\right]&=&\max\limits_{0\leq\zeta\leq
V}\min\limits_{f,t,s,\tau}\left\\{[f+e]\zeta+t:(f,t,s{,\tau})\in\Pi_{+}\right\\}\\\
&=&\min\limits_{f,t,s{,\tau}}\left\\{\max\limits_{0\leq\zeta\leq
V}[f+e]\zeta+t:(f,t,s{,\tau})\in\Pi_{+}\right\\}\\\
&=&\min\limits_{f,t,s{,\tau}}\left\\{\max[0,V(f+e)]+t:(f,t,s{,\tau})\in\Pi_{+}\right\\},\end{array}$

and from (52):

$\begin{array}[]{rcl}\max\limits_{\omega\in{\cal U}}\left[\omega
h-\psi(\omega,v)\right]&=&\max\limits_{0\leq\omega\leq
U}\min\limits_{f,t,s}\left\\{[f+h]\omega+t:(f,t,s)\in\Pi_{-}\right\\}\\\
&=&\min\limits_{f,t,s}\left\\{\max\limits_{0\leq\omega\leq
U}[f+h]\omega+t:(f,t,s)\in\Pi_{-}\right\\}\\\
&=&\min\limits_{f,t,s}\left\\{\max[0,U(f+h)]+t:(f,t,s)\in\Pi_{-}\right\\}.\end{array}$

As a result,

$\begin{array}[]{l}\overline{{\cal
Z}}=\bigg{\\{}(t\in{\mathbf{R}},g=[h;e]\in{\mathbf{R}}^{2},0\leq
x:=[u;v]\leq[U;V]):\exists r,s,f_{\pm},t_{\pm},s_{\pm}{,\tau}:\\\
\lx@intercol\hfil\begin{array}[]{l}t\geq
r+s,r\geq\max[0,V(f_{+}+e)]+t_{+},s\geq\max[0,U(f_{-}+h)]+t_{-}\\\
\,(f_{+},t_{+},s_{+}{,\tau})\in\Pi_{+},\,(f_{-},t_{-},s_{-})\in\Pi_{-}\end{array}\bigg{\\}}.\lx@intercol\end{array}$

Recalling what are $\Pi_{\pm}$, we can straightforwardly represent
$\overline{\cal Z}$ as projection onto the space of $t,g,x$-variables of a set
given by a ${\cal K}$-conic inequality, ending up with an explicit ${\cal
K}$-representation of $\Phi$.

###### Remark 4.2

The just outlined construction can be used in the case of a general convex
Nash Equilibrium problem where, given $n$ convex compact sets ${\cal
X}_{i}\subset{\mathbf{R}}^{k_{i}}$ and $n$ continuously differentiable
functions $\phi_{i}(x_{1},...,x_{n}):\,{\cal X}:={\cal
X}_{1}\times...\times{\cal X}_{n}\to{\mathbf{R}}$ with $\phi_{i}$ convex in
$x_{i}$, concave in $(x_{1},...,x_{i-1},x_{i+1},...,x_{n})$ and such that
$\sum_{i}\phi_{i}$ is convex, one is looking for Nash Equilibria—points
$x^{*}=[x^{*}_{1};...;x^{*}_{n}]\in{\cal X}$ such that for every $i$, the
function $\phi_{i}(x_{1}^{*},...,x_{i-1}^{*},x_{i},x_{i+1}^{*},...,x_{n}^{*})$
attains its minimum over $x_{i}\in{\cal X}_{i}$ at $x_{i}=x_{i}^{*}$. As it
was already mentioned, these equilibria are exactly the weak$=$strong
solutions to ${\mathrm{VI}}(F,{\cal X})$ where the monotone vector field $F$
is given by $F(x_{1},...,x_{n})=\left[{\partial\phi_{1}(x)\over\partial
x_{1}};...;{\partial\phi_{n}(x)\over\partial x_{n}}\right]$. Observing that
the monotone vector fields

$F^{i}(x)=\left[-{\partial\phi_{i}(x)\over\partial
x_{1}};...;-{\partial\phi_{i}(x)\over\partial
x_{i-1}};{\partial\phi_{i}(x)\over\partial
x_{i}};-{\partial\phi_{i}(x)\over\partial
x_{i+1}};...;-{\partial\phi_{i}(x)\over\partial x_{n}}\right]$

associated with convex-concave functions $\phi_{i}$ and the monotone vector
field $F^{0}(x)=\nabla\left(\sum_{i}\phi_{i}(x)\right)$ are linked to $F$ by
the relation $2F=\sum_{i=0}^{n}F^{i}$, we see that in order to get a ${\cal
K}$-representation of $F$, it suffices to have at our disposal ${\cal
K}$-representations of $F^{i}$, $0\leq i\leq n$. These latter representations,
in good cases, can be built according to recipes presented in items 2 and 3 of
Section 4.3.1.

The latter remark puts in proper perspective the “red herring” illustration
which by itself is of no actual interest: setting $s=\sum_{i}x_{i}+1$,
$x\in{\cal X}$ is a Nash Equilibrium if and only if

$c_{i}-{1\over s}+{x_{i}\over s^{2}}={\partial\phi_{i}(x)\over\partial
x_{i}}\left\\{\begin{array}[]{ll}\geq 0,&x_{i}=0\\\ =0,&0<x_{i}<X_{i}\cr\leq
0,&x_{i}=X_{i}.\end{array}\right.$

As a result, finding the equilibrium reduces to solving on the segment
$s\in\big{[}1,\sum_{i}X_{i}+1\big{]}$ the univariate equation

$\sum_{i}x_{i}(s)+1=s,\,x_{i}(s)=\left\\{\begin{array}[]{ll}0,&s(1-sc_{i})<0\\\
s(1-sc_{i}),&0\leq s(1-sc_{i})\leq X_{i}\\\
X_{i},&s(1-sc_{i})>X_{i}.\end{array}\right.$

## Acknowledgment

This work was supported by Multidisciplinary Institute in Artificial
intelligence MIAI @ Grenoble Alpes (ANR-19-P3IA-0003).

## References

  * [1] Aghassia, M., Bertsimas. D., Perakis, G. “Solving asymmetric variational inequalities via convex optimization” – Operations Research Letters 34 (2006) 481–490
  * [2] Andersen, E. D. MOSEK optimization suite, MOSEK ApS, 2019.https://docs.mosek.com/9.2/intro.pdf
  * [3] Boyd, S., Vandenberghe, L. Convex Optimization, Cambridge University Press, 2004. https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf
  * [4] Ben-Tal, A., Nemirovski, A. Lectures on Modern Convex Optimization: Analysis, Algorithms and Engineering Applications, MPS-SIAM Series on Optimization, SIAM, Philadelphia, 2001.
  * [5] Ben-Tal, A., Nemirovski, A. Lectures on Modern Convex Optimization [ISyE GaTech], http://www2.isye.gatech.edu/~nemirovs/LMCOLN2021WithSol.pdf
  * [6] Ghaoui, L., Oks, M., Oustry, F. Worst-case value-at-risk and robust portfolio optimization: A conic programming approach – Operations research, 51(4) 2003, 543–556.
  * [7] Facchinei, F., Pang, J.-S. Finite Dimensional Variational Inequalities and Complementarity Problems, Vol. 1 and 2, Springer, 2003.
  * [8] Goldfarb, D., Iyengar, G. Robust portfolio selection problems – Mathematics of operations research, 28(1) 2003, 1–38.
  * [9] Grant, M., and Boyd, S. CVX: Matlab software for disciplined convex programming, version 2.2, CVX Research, Inc, 2020. http://cvxr.com/cvx/doc/
  * [10] Juditsky, A., Nemirovski, A. Statistical Inference via Convex Optimization, Princeton University Press, 2020. http://www2.isye.gatech.edu/~nemirovs/StatOptPUPWeb.pdf
  * [11] Kojima, M., Megiddo, N., Noma, T., Yoshise, A. A Unified Approach to Interior Point Algorithms for Linear Complementarity Problems, Lecture Notes in Computer Science 538, Springer, 1991.
  * [12] Monteiro, R.D.C., Zanjacomo, P. “General Interior-Point Maps and Existence of Weighted Paths for Nonlinear Semidefinite Complementarity Problems” – Mathematics of Operations Research 25 2000, 381–399.
  * [13] Nesterov, Yu., Nemirovskii, A. Interior-Point Polynomial Algorithms in Convex Programming, SIAM, 1994.
  * [14] Nemirovski, A., Onn, S., Rothblum, U. “Accuracy certificates for computational problems with convex structure” – Mathematics of Operations Research 35:1 2010, 52–78. https://www2.isye.gatech.edu/~nemirovs/MOR_AccuracyCertificates.pdf
  * [15] Nesterov, Yu. “Squared Functional Systems and Optimization Problems” – In: Frenk, H., Roos, C., Terlaky, T., Zhang. S. (Eds.) High Performance Optimization, Springer 2000, 405–440.
  * [16] Petra C. G., Potra F. A. “A homogeneous model for monotone mixed horizontal linear complementarity problems” – Computational Optimization and Applications 72 2019, 241–267.
  * [17] Ralph, D., Wright, S. J. “Superlinear convergence of an interior-point method for monotone variational inequalities” – In Ferris, M. C., Pang, J. S. (Eds.) Complementarity and Variational Problems: State of the Art, SIAM Publications, Philadelphia, 1997, 345–385.
  * [18] Sim, C. K. “Interior point method on semi-definite linear complementarity problems using the Nesterov–Todd (NT) search direction: polynomial complexity and local convergence” – Computational Optimization and Applications 74 2019, 583–621.
  * [19] Toh, K., Todd, M., Tütüncü, R. H. On the implementation and usage of SDPT3–-a Matlab software package for semidefinite-quadratic-linear programming, version 4.0 – In Anjos, M. F., Lasserre, J. B. (Eds.) Handbook on semidefinite, conic and polynomial optimization, Springer, Boston, MA, 2012, 715–754.

##  Appendix A Derivations for Section 4.3

###  A.1 Verification of “raw materials”

  1. 1.

[Affine monotone vector field] Note first that the symmetric part $\bar{A}$ of
$A$ is $\succeq 0$ due to the monotonicity of $F$ on $E$, so that (27) can be
rewritten as a conic constraint on a direct product of properly selected
Lorentz cone and nonnegative orthant, and this direct product belongs to
${\cal K}$. Second, when $t,g,x$ solve (27), for every $y\in E$ one has
$x^{T}Ax=x^{T}\bar{A}x$, whence

$t-y^{T}g=t-y^{T}[Ax+a]=\underbrace{t-x^{T}[Ax+a]}_{=t-x^{T}\bar{A}x-x^{T}a\geq
0}-[y-x]^{T}[Ax+a]\geq[x-y]^{T}[Ax+a]\geq[x-y]^{T}[Ay+a],$

that is, $[t;g;x]\in{\cal F}[F,E]$, as required in item (i) of a
representation of $(F,E)$. Furthermore, when $x\in E$, setting $g=F(x)=Ax+a$
and $t=x^{T}F(x)=x^{T}[Ax+a]=x^{T}[\bar{A}x+a]$, we see that $[t;g;x]$ satisfy
(27), as required in item (ii) of a representation of $(F,E)$.

  2. 2.

[Gradient field of continuously differentiable ${\cal K}$-representable convex
function] Let

$f_{*}(y)=\sup\limits_{x\in{\cal X}}[x^{T}y-f(x)]$

be the Fenchel transform of $f$:

$\begin{array}[]{rcl}f_{*}(y)&=&\sup\limits_{x\in{\cal
X}}[x^{T}y-f(x)]=\sup\limits_{x\in{\cal X},\;s\geq f(x)}[x^{T}y-s]\\\
&=&\sup\limits_{x,u}[x^{T}y-s:Ax+sp+Qu\leq_{{\mathbf{K}}}a]\\\
&=&\min\limits_{\lambda}\left\\{a^{T}\lambda:A^{T}\lambda=y,p^{T}\lambda=-1,Q^{T}\lambda=0,\lambda\geq_{{\mathbf{K}}^{*}}0\right\\}\;\;\hbox{[by
conic duality],}\end{array}$

that is,

$r\geq f_{*}(g)\;\Leftrightarrow\;\exists\lambda:r\geq
a^{T}\lambda,A^{T}\lambda=g,p^{T}\lambda=-1,Q^{T}\lambda=0,\lambda\geq_{{\mathbf{K}}^{*}}0.$
(53)

Next, let

$\begin{array}[]{rclr}{\cal Z}&=&\\{(t,g,x):\exists s,r:\;s\geq f(x),r\geq
f_{*}(g),s+r\leq t\\}&\qquad(a)\\\ &=&\bigg{\\{}(t,g,x):\exists
s,r,u,\lambda:\;\begin{array}[]{l}t\geq s+r,Ax+sp+Qu\leq_{{\mathbf{K}}}a\\\
r\geq
a^{T}\lambda,A^{T}\lambda=g,p^{T}\lambda=-1,Q^{T}\lambda=0,\lambda\geq_{{\mathbf{K}}^{*}}0\end{array}\bigg{\\}}&(b)\\\
\end{array}$ (54)

where $(\ref{jan162}.b)$ is due to (28) and (53). Thus, ${\cal Z}$ is the
projection of the solution set of (29) on the space of $t,g,x$-variables, and
we should check that

(i) ${\cal Z}\subset{\cal F}[f^{\prime}(\cdot),{\cal X}]$, and

(ii) when $x\in{\cal X}$, $g=f^{\prime}(x)$, and $t=x^{T}f^{\prime}(x)$, we
have $[t;g;x]\in{\cal Z}$.

(i): Let $(t,g,x)\in{\cal Z}$. We have $t\geq s+r$ for properly selected
$s\geq f(x)$ and $r\geq f_{*}(g)$, whence for $y\in{\cal X}$ it holds

$t-g^{T}y\geq f(x)+f_{*}(g)-g^{T}y\geq f(x)-f(y)\geq(x-y)^{T}f^{\prime}(y),$

that is, $[t;g;x]\in{\cal F}[f^{\prime}(\cdot),{\cal X}]$. (i) is proved.
(ii): Given $x\in{\cal X}$, let us set $g=f^{\prime}(x)$, $t=x^{T}g$,
$s=f(x)$, $r=f_{*}(g)$. We have

$r=f_{*}(g)=\sup\limits_{x^{\prime}}\\{g^{T}x^{\prime}-f(x^{\prime}):\,x^{\prime}\in{\cal
X}\\}=g^{T}x-f(x)$

(the concluding equality is due to $g=f^{\prime}(x)$); thus, $t=r+s$. Invoking
$(\ref{jan162}.a)$, we conclude that $(t,g,x)\in{\cal Z}$. (ii) is proved.

  3. 3.

[Monotone vector field associated with ${\cal K}$-representable convex-concave
function $\psi$]

##### Verifying $(i)$:

1o. Let us show (33.$a$). Let $(t,g=[h;e],x=[u;v])\in{\cal Z}$, and let $r,s$
be reals which, taken together with $t,g,x$, form a feasible solution to the
system of constraints in (32). For $y=[w;z]\in{\cal X}$ we have

$\begin{array}[]{rcl}t-y^{T}g&\geq&r+s-w^{T}h-z^{T}e\;\;\hbox{[by
(\ref{jan72}.$c$)]}\\\
&\geq&\left[z^{T}e+\psi(u,z)\right]+\left[w^{T}h-\psi(w,v)\right]-w^{T}h-z^{T}e\hbox{\
[by (\ref{jan72}.$a$,$b$)]}\\\
&=&\psi(u,z)-\psi(w,v)=[\psi(u,z)-\psi(w,z)]+[\psi(w,z)-\psi(w,v)]\\\
&\geq&[u-w]^{T}\nabla_{u}\psi(w,z)-[v-z]^{T}\nabla_{v}\psi(w,z)\;\;\hbox{[because
$\psi$ is convex-concave]}\\\ &=&[x-y]^{T}F(y),\\\ \end{array}$

implying that ${\cal Z}\subset{\cal F}[F,{\cal X}]$.
2o. Let us now verify (33.$b$). Given $x=[u;v]\in{\cal X}$, let us set

$g=F(x)=[h;e],\,h=\nabla_{u}\psi(u,v),\,e=-\nabla_{v}\psi(u,v);\,\bar{t}=x^{T}F(x)=h^{T}u+e^{T}v,$

and let $t>\bar{t}$. The function $\zeta^{T}e+\psi(u,\zeta)$ of $\zeta\in{\cal
V}$ is concave, and its gradient w.r.t. $\zeta$ taken at the point $\zeta=v$
vanishes, implying that

$\bar{r}:=v^{T}e+\psi(u,v)\geq\zeta^{T}e+\psi(u,\zeta)\,\,\forall\zeta\in{\cal
V}.$

Similarly, the function $\omega^{T}h-\psi(\omega,v)$ of $\omega\in{\cal U}$ is
concave. and its gradient w.r.t. $\omega$ taken at the point $\omega=u$
vanishes, implying that

$\bar{s}:=u^{T}h-\psi(u,v)\geq\omega^{T}h-\psi(\omega,v)\,\,\forall\omega\in{\cal
U}.$

Observing that $\bar{r}+\bar{s}=\bar{t}<t$, we can find $r>\bar{r}$ and
$s>\bar{s}$ in such a way that $r+s\leq t$. Looking at the constraints
(32.$a$-$c$), we conclude that whenever $x=[u;v]\in{\cal X}$ and
$t>x^{T}F(x)$, the triple $(t,g=F(x),x)$ can be augmented by $r,s$ to satisfy
all constraints (32.$a$-$c$), that is, $(t,g,x)\in{\cal Z}$, as claimed in
(33.$b$).

##### Verifying $(ii)$:

Clearly, all we need in order to justify claim in $(ii)$ is to show that the
set

${\cal Z}^{+}=\left\\{(g=[h;e],x=[u;v],r,s):u\in{\cal U},v\in{\cal
V},r>\max\limits_{z\in{\cal
V}}\left[z^{T}e+\psi(u,z)\right],s>\max\limits_{w\in{\cal
U}}\left[w^{T}h-\psi(w,v)\right]\right\\}$

is the projection of the solution set of the conic constraint

$\left[\begin{array}[]{l}r\geq\theta+\gamma^{T}b{+\tau},\;\eta\geq
0,\;\theta\geq 0,\;\eta\theta\geq 1\\\
s\geq\theta^{\prime}+c^{T}\delta+a^{T}\epsilon,\eta^{\prime}\geq
0,\theta^{\prime}\geq 0,\eta^{\prime}\theta^{\prime}\geq 1\\\
Au+B\alpha\leq_{{\mathbf{K}}}a,\;Cv+D\beta\leq_{{\mathbf{L}}}b,\;Pf+\tau
p+Q\xi+Ru\leq_{{\mathbf{M}}}c\\\
C^{T}\gamma=f+e,D^{T}\gamma=0,\gamma\geq_{{\mathbf{L}}^{*}}0,;\delta\geq_{{\mathbf{M}}^{*}}0,\;\epsilon\geq_{{\mathbf{K}}^{*}}0\\\
P^{T}\delta+v=0,p^{T}\delta=-1,Q^{T}\delta=0,R^{T}\delta+A^{T}\epsilon=h,B^{T}\epsilon=0\end{array}\right]$
(55)

in variables
$x=[u;v],g=[h;e],r,s,\alpha,\beta,\gamma,f,\tau,\xi,\delta,\epsilon,\eta,\theta,\eta^{\prime},$
and $\theta^{\prime}$ on the plane of $g=[h;e],x=[u;v],r,s$-variables. Here is
the proof.
1o. Recall that ${\cal V}$ is convex and compact. Thus, we have

$\begin{array}[]{l}\forall(x=[u;v]\in{\cal X},g=[h;e]):\\\
\max\limits_{z\in{\cal V}}\left[z^{T}e+\psi(u,z)\right]=\max\limits_{z\in{\cal
V}}\left[z^{T}e+\inf\limits_{f,\tau,\xi}\left[f^{T}z+\tau:Pf+\tau
p+Q\xi+Ru\leq_{{\mathbf{M}}}c\right]\right]\hbox{\ [by (\ref{jan71})]}\\\
=\max\limits_{z\in{\cal
V}}\inf\limits_{f,\tau,\xi}\left[(f+e)^{T}z+\tau:Pf+\tau
p+Q\xi+Ru\leq_{{\mathbf{M}}}c\right]\\\
=\inf\limits_{f,\tau,\xi}\left\\{\max\limits_{z\in{\cal
V}}(f+e)^{T}z+\tau:Pf+\tau p+Q\xi+Ru\leq_{{\mathbf{M}}}c\right\\}\
\left[\hbox{by the Sion-Kakutani Theorem}\right]\\\
=\inf\limits_{f,\tau,\xi}\left[\max\limits_{z,\beta}\left[(f+e)^{T}z+\tau:Cz+D\beta\leq_{{\mathbf{L}}}b\right]:Pf+\tau
p+Q\xi+Ru\leq_{{\mathbf{M}}}c\right]\hbox{\ [by (\ref{jan70}.$b$)]}\\\
=\inf\limits_{f,\tau,\xi,\gamma}\left\\{\gamma^{T}b{+\tau}:C^{T}\gamma=f+e,D^{T}\gamma=0,\gamma\geq_{{\mathbf{L}}^{*}}0,Pf+\tau
p+Q\xi+Ru\leq_{{\mathbf{M}}}c\right\\}\\\ \hbox{[by conic duality; recall that
(\ref{jan70}.$b$) is essentially strictly feasible].}\\\ \end{array}$

Together with (30) the latter relation results in

$\displaystyle\big{\\{}(x=[u;v],g=[h;e],r):\,x\in{\cal
X},r>\max\limits_{z\in{\cal V}}\left[z^{T}e+\psi(u,z)\right]\big{\\}}$ (62)
$\displaystyle=\bigg{\\{}(x=[u;v],g=[h;e],r):$ $\displaystyle\exists
f,\tau,\xi,\alpha,\beta,\gamma:$
$\displaystyle\left.\begin{array}[]{l}r>\gamma^{T}b{+\tau},\;Au+B\alpha\leq_{{\mathbf{K}}}a,\;Cv+D\beta\leq_{{\mathbf{L}}}b,\;\gamma\geq_{{\mathbf{L}}^{*}}0\\\
C^{T}\gamma=f+e,\;D^{T}\gamma=0,\;Pf+\tau
p+Q\xi+Ru\leq_{{\mathbf{M}}}c\end{array}\right\\}$
$\displaystyle=\bigg{\\{}(x=[u;v],g=[h;e],r):$ $\displaystyle\exists
f,\tau,\xi,\alpha,\beta,\gamma,\eta,\theta:$
$\displaystyle\left.\begin{array}[]{l}r\geq\gamma^{T}b{+\tau}+\theta,\;\eta\geq
0,\;\theta\geq 0,\;\eta\theta\geq 1\\\
Au+B\alpha\leq_{{\mathbf{K}}}a,\;Cv+D\beta\leq_{{\mathbf{L}}}b,\;,\gamma\geq_{{\mathbf{L}}^{*}},\\\
C^{T}\gamma=f+e,\;D^{T}\gamma=0,\;Pf+\tau
p+Q\xi+Ru\leq_{{\mathbf{M}}}c\end{array}\right\\}.$

2o. When $v\in{\cal V}$ and $h\in{\mathbf{R}}^{n_{u}}$ we have

$\begin{array}[]{l}\max\limits_{w\in{\cal
U}}\left[w^{T}h-\psi(w,v)\right]=\max\limits_{w\in{\cal
U}}\left[w^{T}h+\sup\limits_{f,\tau,\xi}\left[-f^{T}v-\tau:Pf+\tau
p+Q\xi+Rw\leq_{{\mathbf{M}}}c\right]\right]\hbox{\ [by (\ref{jan71})]}\\\
=\sup\limits_{w,f,\tau,\xi,\alpha}\left[w^{T}h-f^{T}v-\tau:Pf+\tau
p+Q\xi+Rw\leq_{{\mathbf{M}}}c,\;Aw+B\alpha\leq_{{\mathbf{K}}}a\right]\hbox{\
[by (\ref{jan70}.$a$)]}\\\
=\min\limits_{\delta,\epsilon}\bigg{\\{}c^{T}\delta+a^{T}\epsilon:\begin{array}[]{l}P^{T}\delta+v=0,\;p^{T}\delta=-1,Q^{T}\delta=0,\;R^{T}\delta+A^{T}\epsilon=h\\\
B^{T}\epsilon=0,\;\delta\geq_{{\mathbf{M}}^{*}}0,\;\epsilon\geq_{{\mathbf{K}}^{*}}0\end{array}\bigg{\\}}\\\
\left[\hbox{\begin{tabular}[]{l}by conic duality; recall that the ${\cal
K}$-representations (\ref{jan70}.$a$)\\\ of ${\cal U}$ and (\ref{jan71}) of
$\psi$ are essentially strictly feasible.\end{tabular}}\right]\end{array}$

Taken together with (30), the latter relation results in

$\displaystyle\big{\\{}(x=[u;v],g=[h;e],s):x\in{\cal
X},s>\max\limits_{w\in{\cal U}}\left[h^{T}w-\psi(w,u)\right]\big{\\}}$ (69)
$\displaystyle=$
$\displaystyle\bigg{\\{}(x=[u;v],g=[h;e],s):\exists\alpha,\beta,\delta,\epsilon:$
$\displaystyle\qquad\qquad\left.\begin{array}[]{l}s>c^{T}\delta+a^{T}\epsilon,\;Au+B\alpha\leq_{{\mathbf{K}}}a,\;Cv+D\beta\leq_{{\mathbf{L}}}b,\;\delta\geq_{{\mathbf{M}}^{*}}0,\;\epsilon\geq_{{\mathbf{K}}^{*}}0\\\
P^{T}\delta+v=0,\;p^{T}\delta=-1,\;Q^{T}\delta=0,\;R^{T}\delta+A^{T}\epsilon=h,\;B^{T}\epsilon=0\end{array}\right\\}$
$\displaystyle=$
$\displaystyle\bigg{\\{}(x=[u;v],g=[h;e],s):\exists\alpha,\beta,\delta,\epsilon,\eta^{\prime},\theta^{\prime}:$
$\displaystyle\qquad\qquad\left.\begin{array}[]{l}s\geq\theta^{\prime}+c^{T}\delta+a^{T}\epsilon,\;\eta^{\prime}\geq
0,\;\theta^{\prime}\geq 0,\;\eta^{\prime}\theta^{\prime}\geq 1\\\
Au+B\alpha\leq_{{\mathbf{K}}}a,\;Cv+D\beta\leq_{{\mathbf{L}}}b,\;\delta\geq_{{\mathbf{M}}^{*}}0,\;\epsilon\geq_{{\mathbf{K}}^{*}}0\\\
P^{T}\delta+v=0,\;p^{T}\delta=-1,\;Q^{T}\delta=0,\;R^{T}\delta+A^{T}\epsilon=h,\;B^{T}\epsilon=0\end{array}\right\\}.$

Finally, (62) and (69) together imply that

$\begin{array}[]{l}{\cal Z}^{+}:=\bigg{\\{}(g=[h;e],x=[u;v],r,s):u\in{\cal
U},v\in{\cal V},{r>\max\limits_{z\in{\cal
V}}\left[z^{T}e+\psi(u,z)\right],s>\max\limits_{w\in{\cal
U}}\left[w^{T}h-\psi(v,u)\right]\bigg{\\}}}\\\
=\bigg{\\{}(g=[h;e],x=[u;v],r,s):\exists
f,\tau,\xi,\alpha,\beta,\gamma,\eta,\theta,\delta,\epsilon,\eta^{\prime},\theta^{\prime}:\\\
\lx@intercol\hfil\qquad\qquad\left.\begin{array}[]{l}r\geq\theta+\gamma^{T}b{+\tau},\eta\geq
0,\theta\geq 0,\eta\theta\geq 1\\\
s\geq\theta^{\prime}+c^{T}\delta+a^{T}\epsilon,\eta^{\prime}\geq
0,\theta^{\prime}\geq 0,\eta^{\prime}\theta^{\prime}\geq 1\\\
Au+B\alpha\leq_{{\mathbf{K}}}a,\;Cv+D\beta\leq_{{\mathbf{L}}}b,\;Pf+\tau
p+Q\xi+Ru\leq_{{\mathbf{M}}}c,\gamma\geq_{{\mathbf{L}}^{*}}0,\delta\geq_{{\mathbf{M}}^{*}}0,\epsilon\geq_{{\mathbf{K}}^{*}}0\\\
C^{T}\gamma=f+e,D^{T}\gamma=0,P^{T}\delta+v=0,p^{T}\delta=-1,Q^{T}\delta=0,R^{T}\delta+A^{T}\epsilon=h,B^{T}\epsilon=0\\\
\end{array}\right\\},\lx@intercol\end{array}$

as claimed in (55).

  4. 4.

[Univariate monotone rational vector field] For evident reasons, it suffices
to consider the case of ${\cal X}=[0,1]$; recall that $\beta(t)>0$ on ${\cal
X}$. Let degrees of $\alpha$ and $\beta$ be $\mu$ and $\nu$, respectively, and
let

$\kappa=\max[\mu,\nu]+1.$

##### 10.

Consider the curves

$\delta(t)=[tF(t);F(t);t]={1\over\beta(t)}[t\alpha(t);\alpha(t);t\beta(t)]:[0,1]\to{\mathbf{R}}^{3},\,\gamma(t)={1\over\beta(t)}\left[1;t;t^{2};...;t^{\kappa}\right]:[0,1]\to{\mathbf{R}}^{\kappa+1}$

For properly selected matrix $A$ we have

$\delta(t)=A\gamma(t),\,0\leq t\leq 1,$

whence

${\cal Y}:=\hbox{\rm Conv}\\{\delta(t),0\leq t\leq 1\\}=A{\cal Z},\,{\cal
Z}=\hbox{\rm Conv}\\{\gamma(t),0\leq t\leq 1\\}.$

We intend to build a semidefinite representation (SDR) of ${\cal Y}$ (i.e.,
${\cal K}$-representation with ${\cal K}$ comprised of finite direct products
of semidefinite cones). Semidefinite representability (and ${\cal
K}$-representability in general) of a set is preserved when taking linear
images: an SDR

${\cal Z}=\\{z:\exists u:{\cal A}(z,u)\succeq 0\\}$ $None$

of ${\cal Z}$ implies the representation

${\cal Y}:=A{\cal Z}=\\{y:\exists[z;u]:y=Az,{\cal A}(z,u)\succeq 0\\},$

and the system of the right hand side constraints can be written down as a
Linear Matrix Inequality in variable $y$ and additional variables $z,u$. Thus,
all we need is to build an SDR of ${\cal Z}$.

##### 20.

We shall get SDR of ${\cal Z}$ from SDR of the “support cone”

${\cal P}=\\{[p;q]\in{\mathbf{R}}^{\kappa+1}\times{\mathbf{R}}:\min_{z\in{\cal
Z}}p^{T}z-q\geq 0\\}=\\{[p;q]:\min_{0\leq t\leq 1}p^{T}\gamma(t)\geq q\\}$

of ${\cal Z}$.

Given $p=[p_{0};p_{1};...;p_{\kappa+1}]\in{\mathbf{R}}^{\kappa+1}$, let, with
a slight abuse of notation, $p(t)=\sum_{i=0}^{\kappa}p_{i}t^{i}$ be the
polynomial with coefficients $p_{i}$, $0\leq i\leq\kappa$. We have

$\begin{array}[]{l}[p;q]\in{\cal P}\Leftrightarrow{p(t)\over\beta(t)}\geq
q\,\forall t\in[0,1]\\\
\Leftrightarrow{(1+\tau^{2})^{\kappa}p(\tau^{2}/(1+\tau^{2}))\over(1+\tau^{2})^{\kappa}\beta(\tau^{2}/(1+\tau^{2}))}\geq
q\;\forall\tau\in{\mathbf{R}}\\\
\Leftrightarrow\underbrace{(1+\tau^{2})^{\kappa}p(\tau^{2}/(1+\tau^{2}))-q(1+\tau^{2})^{\kappa}\beta(\tau^{2}/(1+\tau^{2}))}_{=:\pi_{p,q}(\tau)}\geq
0\;\forall\tau\in{\mathbf{R}}.\end{array}$

Note that $\pi_{p,q}(\tau)$ is a polynomial of $\tau$ of degree $\leq
2\kappa$, and the vector $\pi_{p,q}$ of coefficients of polynomial is linear
in $[p;q]$: $\pi_{p,q}=P[p;q]$. We see that ${\cal P}$ is the inverse image of
the cone ${\cal P}_{2\kappa}$ of coefficients of polynomials of degree $\leq
2\kappa$ which are nonnegative on the entire axis:

${\cal P}=\\{[p;q]:P[p;q]\in{\cal P}_{2\kappa}\\}.$

As was observed by Yu. Nesterov [15], the cone ${\cal P}_{2\kappa}$ is the
linear image of the semidefinite cone ${\mathbf{S}}^{\kappa+1}_{+}$:

${\cal P}_{2\kappa}=\\{\pi\in{\mathbf{R}}^{2\kappa+1}:\exists
x=[x_{ij}]_{0\leq i,j\leq\kappa}\in{\mathbf{S}}^{\kappa+1}_{+}:[{\cal
Q}x]_{\ell}:=\sum\limits_{{0\leq i,j\leq\kappa,\atop
i+j=\ell}}x_{ij}=\pi_{\ell},0\leq\ell\leq 2\kappa\\},$

and we arrive at a semidefinite representation of ${\cal P}$:

${\cal P}=\\{[p;q]:\exists x\in{\mathbf{S}}^{\kappa+1}:x\succeq 0\ \&\ {\cal
Q}x=P[p;q]\\}.$ (70)

We claim that this representation is essentially strictly feasible. Indeed,
let $\bar{p}=[1;1;...;1]\in{\mathbf{R}}^{\kappa+1}$ and $\bar{q}=0$. Then

$\pi_{\bar{p},\bar{q}}(\tau)=(1+\tau^{2})^{\kappa}\left[1+\tau^{2}/(1+\tau^{2})+[\tau^{2}/(1+\tau^{2})]^{2}+...+[\tau^{2}/(1+\tau^{2})]^{\kappa}\right]=\sum_{i=0}^{\kappa}c_{i}\tau^{2i},\,c_{i}>0\,\forall
i,$

implying that with $\bar{x}=\hbox{\rm
Diag}\\{c_{0},c_{1},...,c_{\kappa}\\}\in{\mathbf{S}}^{\kappa+1}$ one has

$P[\bar{p};\bar{q}]={\cal Q}\bar{x}\ \&\ \bar{x}\succ 0.$

That is, $\bar{p},\bar{q}$, and $\bar{x}$ satisfy all constraints in (70) and
strictly satisfy the non-polyhedral constraint $x\succeq 0$, as required by
essentially strict feasibility.

##### 30.

Now we are done: by its origin, ${\cal Z}$ is a convex compact set and as such
is convex and closed, implying by duality that

$\begin{array}[]{rcl}{\cal Z}&=&\\{z\in{\mathbf{R}}^{\kappa+1}:p^{T}z-q\geq
0\,\,\forall[p;q]\in{\cal P}\\}\\\
&=&\Big{\\{}z\in{\mathbf{R}}^{\kappa+1}:\inf\limits_{p,q,x}\\{[p^{T}z-q]:P[p;q]-{\cal
Q}x=0,x\succeq 0\\}{\geq 0\Big{\\}}}\;\;\hbox{[by(\ref{sdpP})]}\\\
&=&\Big{\\{}z\in{\mathbf{R}}^{\kappa+1}:\exists\lambda\in{\mathbf{R}}^{2\kappa+1}:P^{T}\lambda=[z;-1],{\cal
Q}^{*}\lambda\succeq 0\Big{\\}}\\\ &&\hbox{[by semidefinite duality;
$\lambda\mapsto{\cal
Q}^{*}\lambda:{\mathbf{R}}^{2\kappa+1}\to{\mathbf{S}}^{\kappa+1}$}\\\
&&\hbox{is the conjugate of $x\mapsto{\cal
Q}x:{\mathbf{S}}^{\kappa+1}\to{\mathbf{R}}^{2\kappa+1}$],}\end{array}$

and we arrive at the desired SDR of ${\cal Z}$.

###  A.2 Verification of calculus rules

  1. 1.

[Restriction on a ${\cal K}$-representable set] Let (35) represent $(F,{\cal
X})$. Suppose that $[t;g;x]$ can be augmented by $u,v$ to solve (37). Then
$(t,g,x,u)$ solve (35), implying that $[t;g;x]\in{\cal F}[F,{\cal X}]$ by
definition of ${\cal K}$-representability of $(F,{\cal X})$, and $(x,v)$ solve
(37), implying that $x\in{\cal Y}$. Taking together, these inclusions clearly
imply that $[t;g;x]\in{\cal F}[\bar{F},{\cal Z}]$, as required in item (i) of
the definition of ${\cal K}$-representation of $(\bar{F},{\cal Z})$. Next,
when $x\in{\cal Z}$, the triple $[t:=\langle F(x),x\rangle;g:=F(x);x]$ can be
augmented by $u$ to solve (35) (by item (ii) of the definition of ${\cal
K}$-representation of $(F,{\cal X})$), and because $x\in{\cal Y}$, $x$ can be
augmented by $v$ to solve (36). Thus, $t:=\langle F(x),x\rangle$, $g:=F(x)$,
$x$ can be augmented by $(u,v)$ to solve (37), as required in item (ii) of
${\cal K}$-representability of $(\bar{F},Z)$. Thus, (37) indeed represents
$(\bar{F},{\cal Z})$. A completely similar reasoning shows that if (35) almost
represents $(F,{\cal X})$, then (37) almost represents $(\bar{F},{\cal Z})$.

  2. 2.

[Direct summation] When $x=[x_{1};...;x_{K}]\in{\cal X}$ and
$g=F(x)=[g_{1};...;g_{K}]$, $g_{k}=F_{k}(x_{k})$, $t_{k}=\langle
x_{k},g_{k}\rangle$ and $t=\sum_{k}t_{k}=\langle g,x\rangle$, there exist
$u_{k}$ such that (39.$a$) take place (by item (ii) of the definition of
representation as applied to the representations in (38)), and (39.$b$) takes
place as well, as required in item (ii) of the definition of a representation
of $(F,{\cal X})$. On the other hand, when $x=[x_{1};...;x_{K}]$,
$g=[g_{1};...;g_{k}]$, and $t$ can be augmented by $u_{k}$ and $t_{k}$ to
solve $(\ref{jan66}.a)$ and $(\ref{jan66}.b)$, we have
$[t_{k};g_{k};x_{k}]\in{\cal F}[F_{k},{\cal X}_{k}]$, $k\leq K$, whence for
every $y=[y_{1};...;y_{K}]\in{\cal X}$ it holds

$t_{k}-\langle g_{k},y_{k}\rangle\geq\langle
F_{k}(y_{k}),x_{k}-y_{k}\rangle,\,k\leq K.$

When summing up the above inequalities over $k$, we get

$t-\langle g,y\rangle\geq\langle F(y),x-y\rangle\,\forall y\in{\cal X},$

that is, $[t;g;x]\in{\cal F}[F,{\cal X}]$, as required in item (i) of the
definition of a representation of $(F,{\cal X})$.
The above reasoning, with evident modifications, shows the claim in the case
of almost representations.

  3. 3.

[Taking conic combinations] Let $t,g,x$ can be augmented by
$u_{k},t_{k},g_{k},k\leq K$ to solve (41). Then $[t_{k};g_{k};x]\in{\cal
F}[{\cal F}_{k},{\cal X}]$, implying that

$t_{k}-\langle g_{k},y\rangle\geq\langle F_{k}(y),x-y\rangle\,\,\forall y\in
X;$

multiplying both sides by $\alpha_{k}$ and summing up over $k$, we get

$t-\langle g,y\rangle\geq\langle F(y),x-y\rangle\,\forall y\in X,$

that is, $[t;g;x]\in{\cal F}[F,{\cal X}]$. On the other hand, given $x\in{\cal
X}$, let us set $g_{k}=F_{k}(x)$ and $t_{k}=\langle F_{k}(x),x\rangle$. Since
the $k$-th conic constraint in (41) represents $(F_{k},{\cal X})$, there exist
$u_{k}$, $k\leq K$, such that all relations (41.$a$) take place. Setting
$t=\sum_{k}\alpha_{k}t_{k}$, $g=\sum_{k}\alpha_{k}g_{k}$, we, on one hand,
satisfy (41.$b$-$c$), and, on the other hand, obtain

$t=\sum_{k}\alpha_{k}\langle F_{k}(x),x\rangle=\langle
F(x),x\rangle,\,\,g=\sum_{k}\alpha_{k}g_{k}=F(x),$

the bottom line being that $[\langle F(x),x\rangle;F(x);x]$ can be augmented
by $u_{k}$, $t_{k}$, $g_{k}$ to solve (41). Thus, (41) indeed is a ${\cal
K}$-representation of $(F,{\cal X})$.
The above reasoning, with evident modifications, works in the case of almost
representations.

  4. 4.

[Affine substitution of variables] Assume that $\tau,\gamma,\xi,g,t,u$ solve
(43). Then $t$, $g$, $x:=A\xi+a$, $u$ satisfy

$Xx+Gg+tT+Uu\leq_{{\mathbf{K}}}a,$

implying that $x\in{\cal X}$ and

$t-\langle g,y\rangle\geq\langle F(y),x-y\rangle\,\,\forall y\in{\cal X}.$

Recall that $x=A\xi+a$, $x\in{\cal X}$, implies that $\xi\in\Xi$. Now, when
$\eta\in\Xi$, setting $y=A\eta+a$, we have $y\in{\cal X}$ and

$\begin{array}[]{rcl}\tau-\langle\gamma,\eta\rangle&=&t-\langle
g,a\rangle-\langle A^{T}g,\eta\rangle=t-\langle g,y\rangle\geq\langle
F(y),x-y\rangle\\\ &=&\langle
F(A\eta+a),A(\xi-\eta)\rangle=\langle\Phi(\eta),\xi-\eta\rangle,\\\
\end{array}$

and since $\eta\in\Xi$ is arbitrary, we get $[\tau;\gamma;\xi]\in{\cal
F}[\Phi,\Xi]$, as required in item (i) of the definition of a representation
of $(\Phi,\Xi)$. On the other hand, when $\xi\in\Xi$, $\gamma=\Phi(\xi)$, and
$\tau=\langle\Phi(\xi),\xi\rangle$, setting $x=A\xi+a$, we get $x\in{\cal X}$.
Next, when setting $g=F(x)$, $t=\langle F(x),x\rangle$, we obtain
$\gamma=A^{T}g$ and

$\tau=\langle F(x),x-a\rangle=t-\langle g,a\rangle.$

Besides this, by the origin of $t,g,x$ and item (ii) of the definition of
${\cal K}$-representation, as applied to (42), there exists $u$ such that
$t,g,x,u$ satisfy (42). The bottom line is that $\xi,\gamma,\tau$ can be
augmented by $t,g,u$ to solve (43), that is, (43) meets item (ii) of
definition of ${\cal K}$-representation of $(\Phi,\Xi)$.
The above reasoning, with evident modifications, works in the case of almost
representations.

##  Appendix B Verifying (51) and (52)

A. Let us prove that for all $u\in{\cal U}=[0,U]$, $v\in{\cal V}=[0,V]$ one
has

$\displaystyle\psi(u,v)$ $\displaystyle=$ $\displaystyle-{u\over u+v+1}$
$\displaystyle=$ $\displaystyle\min\limits_{f,t,s}\left\\{fv+t:\,1\geq f\geq
0,\,0\leq s\leq\sqrt{uf},\,s+{1\over u+1}\leq 1,\,t-f\geq(1-s)^{2}-1,\,t\leq
1\right\\}$ $\displaystyle=$
$\displaystyle\min\limits_{f,t,s;,\tau}\left\\{fv+t:\,\begin{array}[]{l}1\geq
f\geq 0,\,s\geq 0,\,t\leq 1,\,\tau\geq 0,\,s+\tau\leq 1\\\
\underbrace{[2s;u-f;u+f]\in{\mathbf{L}}^{3}}_{\Leftrightarrow s^{2}\leq
uf\hbox{\tiny\ when $u+f\geq 0$}}\\\
\underbrace{[2(1-s);t-f;t-f+2]\in{\mathbf{L}}^{3}}_{\Leftrightarrow(1-s)^{2}\leq
t-f+1\hbox{\tiny\ when $t-f+2\geq 0$}}\\\
\underbrace{[2;u-\tau+1;u+\tau+1]\in{\mathbf{L}}^{3}}_{\Leftrightarrow(u+1)\tau\geq
1\hbox{\tiny\ when $u+\tau+1\geq 0$}}\end{array}\right\\}.$

Indeed, for $u\in{\cal U}$ and $v\in{\cal V}$ we have

$\begin{array}[]{l}\min\limits_{f,t,s}\left\\{fv+t:\,1\geq f\geq 0,0\leq
s\leq\sqrt{uf},s+{1\over u+1}\leq 1,t-f\geq(1-s)^{2}-1,t\leq 1\right\\}\\\
=\min\limits_{f}\left\\{fv+f-2\bar{s}(f)+\bar{s}(f)^{2}:\,1\geq f\geq
0,\,\bar{s}(f)=\min\left[{u\over u+1},\sqrt{uf}\right]\right\\}\\\
=\min\left[\min\limits_{0\leq f\leq
u/(u+1)^{2}}\left\\{fv+f-2\sqrt{uf}+uf\right\\},\min\limits_{1\geq f\geq
u/(u+1)^{2}}\left\\{fv+f-{2u\over
u+1}+{u^{2}\over(u+1)^{2}}\right\\}\right]\\\ =\min\left[-{u\over
u+v+1},{u(v+1)-2u-u^{2}\over(u+1)^{2}}\right]=u\min\left[-{1\over
v+(u+1)},{v-(u+1)\over(u+1)^{2}}\right]={u\over
v+u+1}\min\left[-1,{v^{2}-(u+1)^{2}\over(u+1)^{2}}\right]\\\ =\psi(u,v),\\\
\end{array}$

as claimed.

B. Now let us show that for all $u\in{\cal U}=[0,U]$, $v\in{\cal V}=[0,V]$

$\displaystyle-\psi(u,v)$ $\displaystyle:=$ $\displaystyle{u\over u+v+1}$
$\displaystyle=$ $\displaystyle\min\limits_{f,t,s}\left\\{fu+t:1\geq f\geq
0,\,0\leq s\leq\sqrt{(v+1)f},\,s\leq 1,\,1\geq t\geq(1-s)^{2}\right\\}$
$\displaystyle=$
$\displaystyle\min\limits_{f,t,s}\left\\{fu+t:\begin{array}[]{l}1\geq f\geq
0,\,0\leq s\leq 1,\,t\leq 1\\\
\underbrace{[2s;v+1-f;v+1+f]\in{\mathbf{L}}^{3}}_{\Leftrightarrow
s^{2}\leq(v+1)f\hbox{\tiny\ when $v+1+f\geq 0$}}\\\
\underbrace{[2(1-s);t-1;t+1]\in{\mathbf{L}}^{3}}_{\Leftrightarrow(1-s)^{2}\leq
t}\\\ \end{array}\right\\}$

Indeed, for $u\in{\cal U}$ and $v\in{\cal Q}$ we have

$\begin{array}[]{l}\min\limits_{f,t,s}\left\\{fu+t:1\geq f\geq 0,0\leq
s\leq\sqrt{(v+1)f},s\leq 1,1\geq t\geq(1-s)^{2}\right\\}\\\
=\min\limits_{f,s}\left\\{fu+(1-s)^{2}:1\geq f\geq 0,0\leq
s\leq\sqrt{(v+1)f},s\leq 1\right\\}\\\
=\min\limits_{f}\left\\{fu+(1-\bar{s}(f))^{2}:1\geq f\geq
0,\bar{s}(f)=\min[\sqrt{(v+1)f},1]\right\\}\\\ =\min\left[\min\limits_{0\leq
f\leq 1/(v+1)}\\{fu+1-2\sqrt{(v+1)f}+(v+1)f\\},\,\min\limits_{1\geq f\geq
1/(v+1)}\\{fu\\}\right]\\\ =\min\left[{u\over u+v+1},{u\over
v+1}\right]={u\over u+v+1}=-\psi(u,v),\\\ \end{array}$

as claimed. $\square$