Dependencies

The closed convex hull of a nonempty set \(S\subset \mathbb {R}^n\) is the intersection of all closed convex sets containing \(S\). It will be denoted by \(\overline{\operatorname {co}}\, S\).

Let \(x\in \operatorname {cl}C\) and \(x'\in \operatorname {ri}C\). Then the half-open segment

is contained in \(\operatorname {ri}C\).

For \(i=1,\ldots ,k\), let \(C_i\subset \mathbb {R}^{n_i}\) be convex sets. Then

A nonempty convex subset \(F\subset C\) is a face of \(C\) if it satisfies the following property: every segment of \(C\), having in its relative interior an element of \(F\), is entirely contained in \(F\). In other words,

The direction \(s\in \mathbb {R}^n\) is said normal to \(C\) at \(x\in C\) when

The set of all such directions is called normal cone to \(C\) at \(x\), denoted by \(N_C(x)\).

For given \(x\in C\) and \(d\in \mathbb {R}^n\), there holds

Let \(f\in \operatorname {Conv}\mathbb {R}^n\) [resp. \(\overline{\operatorname {Conv}}\mathbb {R}^n\)] and let \(g\in \operatorname {Conv}\mathbb {R}\) [resp. \(\overline{\operatorname {Conv}}\mathbb {R}\)] be increasing. Assume that there is \(x_0\in \mathbb {R}^n\) such that \(f(x_0)\in \operatorname {dom}g\), and set \(g(+\infty ):=+\infty \). Then the composite function \(g\circ f:\; x\mapsto g(f(x))\) is in \(\operatorname {Conv}\mathbb {R}^n\) [resp. in \(\overline{\operatorname {Conv}}\mathbb {R}^n\)].

Let \(f_1\) and \(f_2\) be two functions from \(\mathbb {R}^n\) to \(\mathbb {R}\cup \{ +\infty \} \). Their infimal convolution is the function from \(\mathbb {R}^n\) to \(\mathbb {R}\cup \{ \pm \infty \} \) defined by

Let \(f\in \operatorname {Conv}\mathbb {R}^n\). All the nonempty sublevel-sets of \(f\) have the same asymptotic cone, which is the sublevel-set of \(f^\infty \) at the level \(0\):

In particular, the following statements are equivalent:

1. There is \(r\) for which \(S_r(f)\) is nonempty and compact;

2. all the sublevel-sets of \(f\) are compact;

3. \(f^\infty _\circ (d){\gt}0\) for all nonzero \(d\in \mathbb {R}^n\).

Let \(C\subset \mathbb {R}^n\) be convex. The mapping \(F: C\to \mathbb {R}^n\) is said to be monotone [resp. strictly monotone, resp. strongly monotone with modulus \(c{\gt}0\)] on \(C\) when, for all \(x\) and \(x'\) in \(C\),

[resp. \(\langle F(x)-F(x'),\, x-x'\rangle {\gt} 0\) whenever \(x\neq x'\), resp. \(\langle F(x)-F(x'),\, x-x'\rangle \ge c\| x-x'\| ^2\)].

The conjugate of a function \(f\) satisfying (1.1.1) is the function \(f^{*}\) defined by

For simplicity, we may also let \(x\) run over the whole space instead of \(\operatorname {dom}f\).

The mapping \(f\mapsto f^{*}\) will often be called the conjugacy operation, or the Legendre–Fenchel transform.

A function \(f\) satisfying (1.1.1) is said to be coercive [resp. 1-coercive] when

Let \(g\in \operatorname {Conv}\mathbb {R}^m\) be such that \(0\in \text{dom }g\) and let \(A_0\) be linear from \(\mathbb {R}^n\) to \(\mathbb {R}^m\). Make the following assumption:

Then \((g\circ A_0)^* = A_0^* g^*\); for every \(s\in \text{dom }(g\circ A_0)^*\), the problem

has at least one optimal solution \(\bar p\) and there holds \((g\circ A_0)^*(s)=A_0^*g^*(s)=g^*(\bar p)\).

For \(t \ge 1\):

The projected subgradient descent algorithm with time-varying step size \((\eta _t)_{t\ge 1}\), that is

Let \(\mathcal X\) be a convex set with non-empty interior, and \(f\) a \(C^3\) convex function defined on \(\operatorname {int}(\mathcal X)\). Then \(f\) is self-concordant (with constant \(M\)) if for all \(x\in \operatorname {int}(\mathcal X)\), \(h\in \mathbb R^n\),

We say that \(f\) is standard self-concordant if \(f\) is self-concordant with constant \(M=2\).

Let \(C_1,\, C_2\) be two nonempty closed convex sets with \(C_1\cap C_2=\varnothing \). If \(C_2\) is bounded, there exists \(s\in \mathbb {R}^n\) such that

The data \((s_j,r_j)\in \mathbb {R}^n\times \mathbb {R}\) for \(j\) in an arbitrary index set \(J\) is equivalent to the data of a closed convex set \(C\) via the relation

The tangent cone is the polar of the normal cone:

With the above notation, suppose that \(g\) is bounded below on the set \(\{ x\} \times \mathbb {R}^m\), for all \(x\in \mathbb {R}^n\). Then the marginal function \(\gamma \) lies in \(\operatorname {Conv}\mathbb {R}^n\).

If \(\sigma \) is sublinear, then

C is compact if and only if \(\gamma _C(x){\gt}0\) for all \(x\neq 0\).

For a nonempty closed convex set \(S\) and a closed sublinear function \(\sigma \), the following are equivalent:

1. \(\sigma \) is the support function of \(S\).

2. \(S=\{ s:\ \langle s,d\rangle \le \sigma (d)\text{ for all }d\in X\} ,\) where the set \(X\) can be indifferently taken as: the whole of \(\mathbb {R}^n\), the unit ball \(B(0,1)\) or its boundary, or \(\operatorname {dom}\sigma \).

Let \(C\) be a closed convex set containing the origin. Its support function \(\sigma _C\) is the gauge of \(C^\circ \).

Let \((S_k)\) be a sequence of nonempty convex compact sets and \(S\) a nonempty convex compact set. When \(k \to +\infty \), the following are equivalent

1. \(S_k \to S\) in the Hausdorff sense, i.e. \(\Delta _H(S_k,S)\to 0\);

2. \(\sigma _{S_k}\to \sigma _S\) pointwise;

3. \(\sigma _{S_k}\to \sigma _S\) uniformly on each compact set of \(\mathbb {R}^n\).

Let \(f:\mathbb {R}^n\to \mathbb {R}\) be convex. At any \(x\),

whenever one of the following equivalent properties holds:

If the convex \(f\) is (Gâteaux) differentiable at \(x\), its only subgradient at \(x\) is its gradient \(\nabla f(x)\). Conversely, if \(\partial f(x)\) contains only one element \(s\), then \(f\) is (Fréchet) differentiable at \(x\), with \(\nabla f(x)=s\).

The notation and assumptions are those of Theorem 4.4.2. Assume also that each \(f_j\) is differentiable; then

For some compact set \(Y\subset \mathbb {R}^p\), let \(g:\mathbb {R}^n\times Y\to \mathbb {R}\) be a function satisfying the following properties:

• for each \(x\in \mathbb {R}^n\), \(g(x,\cdot )\) is upper semi-continuous;

• for each \(y\in Y\), \(g(\cdot ,y)\) is convex and differentiable;

• the function \(f:=\sup _{y\in Y} g(\cdot ,y)\) is finite-valued on \(\mathbb {R}^n\);

• at some \(x\in \mathbb {R}^n\), \(g(x,\cdot )\) is maximized at a unique \(y(x)\in Y\).

Then \(f\) is differentiable at this \(x\), and its gradient is

(where \(\nabla _x g(x,y)\) denotes the gradient of the function \(g(\cdot ,y)\) at \(x\)).

Make the assumptions of Theorem 4.5.1. If \(g\) is differentiable at some \(y\in Y(x)\), then \(Ag\) is differentiable at \(x\).

Suppose that the subdifferential of \(g\) in (4.5.4) is associated with a scalar product \(\langle \! \langle \cdot ,\cdot \rangle \! \rangle \) preserving the structure of a product space:

At a given \(x\in \mathbb {R}^n\), take an arbitrary \(y\) solving (4.5.4). Then

Let \(f_1\) and \(f_2:\mathbb {R}^n\to \mathbb {R}\) be two convex functions minorized by a common affine function. For given \(x\), let \((y_1,y_2)\) be such that the inf-convolution is exact at \(x=y_1+y_2\), i.e.: \((f_1\mathbin {\square }f_2)(x)=f_1(y_1)+f_2(y_2)\). Then

For \(f:\mathbb {R}^n\to \mathbb {R}\) convex, the function \(f'(\cdot ,d)\) is upper semicontinuous: at all \(x\in \mathbb {R}^n\),

Let \((f_k)\) be a sequence of (finite) differentiable convex functions converging pointwise to the differentiable \(f:\mathbb {R}^n\to \mathbb {R}\). Then \(\nabla f_k\) converges to \(\nabla f\) uniformly on every compact set of \(\mathbb {R}^n\).

If \(g\) is a function satisfying \(\overline{\operatorname {co}}\, f \le g \le f\), then \(g^* = f^*\). The function \(f\) is equal to its biconjugate \(f^{**}\) if and only if \(f\in \overline{\operatorname {Conv}}\mathbb {R}^n\).

With \(g:\mathbb {R}^n\times \mathbb {R}^p=\mathbb {R}^m\to \mathbb {R}\cup \{ +\infty \} \) not identically \(+\infty \), let \(g^*\) be associated with a scalar product preserving the structure of \(\mathbb {R}^m\) as a product space: \(\langle \cdot ,\cdot \rangle _m=\langle \cdot ,\cdot \rangle _n+\langle \cdot ,\cdot \rangle _p\). If there exists \(s_0\in \mathbb {R}^n\) such that \((s_0,0)\in \operatorname {dom} g^*\), then the conjugate of \(f\) defined by (2.1.2) is

Let \(f_1\) and \(f_2\) be two functions from \(\mathbb {R}^n\) to \(\mathbb {R}\cup \{ +\infty \} \), not identically \(+\infty \), and satisfying \(\operatorname {dom} f_1^*\cap \operatorname {dom} f_2^*\neq \varnothing \). Then their inf-convolution satisfies (1.1.1), and \((f_1\mathbin {\square }f_2)^*=f_1^*+f_2^*\).

Let \(f:\mathbb {R}^n\to \mathbb {R}\) be strictly convex, differentiable and 1-coercive. Then

1. \(f^{*}\) is also finite-valued on \(\mathbb {R}^n\), strictly convex, differentiable and 1-coercive;

2. the continuous mapping \(\nabla f\) is one-to-one from \(\mathbb {R}^n\) onto \(\mathbb {R}^n\), and its inverse is continuous;

Let \(f\) be a standard self-concordant function on \(\mathcal{X}\). For \(x\in \operatorname {int}(\mathcal{X})\), we say that \(\lambda _f(x)=\| \nabla f(x)\| _{x}^*\) is the Newton decrement of \(f\) at \(x\).

\(F\) is a \(\nu \)-self-concordant barrier if it is a standard self-concordant function, and it is \(\tfrac {1}{\nu }\)-exp-concave.

\(F:\operatorname {int}(\mathcal{X})\to \mathbb {R}\) is a barrier for \(\mathcal{X}\) if

In mirror descent the projection is done via the Bregman divergence associated to \(\Phi \). Precisely one defines

We consider the following simple iterative algorithm: let \(S_1=\mathcal{X}\), and for \(t\ge 1\) do the following:

1. Compute

   \begin{equation} c_t=\frac{1}{\operatorname {vol}(S_t)}\int _{x\in S_t} x\, dx. \label{eq:2.1} \end{equation}

   1

2. Query the first order oracle at \(c_t\) and obtain \(w_t\in \partial f(c_t)\). Let

   \[ S_{t+1}=S_t\cap \{ x\in \mathbb {R}^n:(x-c_t)^\top w_t\le 0\} . \]

If stopped after \(t\) queries to the first order oracle then we use \(t\) queries to a zeroth order oracle to output

This procedure is known as the center of gravity method, it was discovered independently on both sides of the Wall by Levin [1965] and Newman [1965].

Let \(x_1 = y_1\) an arbitrary initial point, and

The conditional gradient descent, introduced in Frank and Wolfe [1956], performs the following update for \(t\ge 1\), where \((\gamma _s)_{s\ge 1}\) is a fixed sequence,

The mirror descent strategy based on a mirror map \(\Phi \) is as follows: let \(x_1\in \operatorname*{arg\, min}_{x\in \mathcal{X}\cap \mathcal{D}}\Phi (x)\). Then for \(t\ge 1\), let \(y_{t+1}\in \mathcal{D}\) such that

and

Let \(\mathcal{D}\subset \mathbb {R}^n\) be a convex open set such that \(\mathcal{X}\) is included in its closure, that is \(\mathcal{X}\subset \overline{\mathcal{D}}\), and \(\mathcal{X}\cap \mathcal{D}\neq \varnothing \). We say that \(\Phi :\mathcal{D}\to \mathbb {R}\) is a mirror map if it satisfies the following properties:

1. \(\Phi \) is strictly convex and differentiable.

2. The gradient of \(\Phi \) takes all possible values, that is \(\nabla \Phi (\mathcal{D})=\mathbb {R}^n\).

3. The gradient of \(\Phi \) diverges on the boundary of \(\mathcal{D}\), that is

   \[ \lim _{x\to \partial \mathcal{D}}\| \nabla \Phi (x)\| =+\infty . \]

Mirror prox is described by the following equations:

Nesterov’s accelerated gradient descent can be described as follows: Start at an arbitrary initial point \(x_1=y_1\) and then iterate the following equations for \(t\ge 1\),

Nesterov’s accelerated gradient descent for the case \(\alpha = 0\). First we define the following sequences:

(Note that \(\gamma _t \le 0\).) Now the algorithm is simply defined by the following equations, with \(x_1 = y_1\) an arbitrary initial point,

The set \(C \subset \mathbb {R}^n\) is said to be convex if \( \alpha x + (1-\alpha )x'\) is in \(C\) whenever \(x\) and \(x'\) are in \(C\), and \(\alpha \in ]0,1[\) (or equivalently \(\alpha \in [0,1]\)).

A convex combination of elements \(x_1,\ldots ,x_k\) in \(\mathbb {R}^n\) is an element of the form

where

A conical combination of elements \(x_1,\dots ,x_k\) is an element of the form \(\sum _{i=1}^k \alpha _i x_i\), where the coefficients \(\alpha _i\) are nonnegative.

The set of all conical combinations from a given nonempty \(S\subset \mathbb {R}^n\) is the conical hull of \(S\). It is denoted by \(\operatorname {cone} S\).

The closed conical hull (or rather closed convex conical hull) of a nonempty set \(S\subset \mathbb {R}^n\) is

The relative interior \(\operatorname {ri} C\) (or \(\operatorname {relint} C\)) of a convex set \(C \subset \mathbb {R}^n\) is the interior of \(C\) for the topology relative to the affine hull of \(C\). In other words: \(x \in \operatorname {ri} C\) if and only if

The dimension of a convex set \(C\) is the dimension of its affine hull, that is to say the dimension of the subspace parallel to \(\operatorname {aff} C\).

The asymptotic cone, or recession cone of the closed convex set \(C\) is the closed convex cone \(C_{\infty }\) defined by (2.2.1) or (2.2.2), in which Proposition 2.2.1 is exploited.

We say that \(x\in C\) is an extreme point of \(C\) if there are no two different points \(x_1\) and \(x_2\) in \(C\) such that \(x=\tfrac {1}{2}(x_1+x_2)\).

An affine hyperplane \(H_{s,r}\) is said to support the set \(C\) when \(C\) is entirely contained in one of the two closed half-spaces delimited by \(H_{s,r}\): say

It is said to support \(C\) at \(x\in C\) when, in addition, \(x\in H_{s,r}\); (2.4.1) holds, as well as

The set \(F\subset C\) is an exposed face of \(C\) if there is a supporting hyperplane \(H_{s,r}\) of \(C\) such that \(F=C\cap H_{s,r}\).

An exposed point, or vertex, is a \(0\)-dimensional exposed face, i.e. a point \(x\in C\) at which there is a supporting hyperplane \(H_{s,r}\) of \(C\) such that \(H_{s,r}\cap C\) reduces to \(\{ x\} \).

Let \(K\) be a convex cone, as defined in Example 1.1.4. The polar cone of \(K\) (called negative polar cone by some authors) is:

A closed convex polyhedron is an intersection of finitely many half-spaces. Take \((s_1,r_1),\ldots ,(s_m,r_m)\) in \(\mathbb {R}^n\times \mathbb {R}\), with \(s_i\neq 0\) for \(i=1,\ldots ,m\); then define

or in matrix notations (assuming the dot-product for \(\langle \cdot ,\cdot \rangle \)),

if \(A\) is the matrix whose rows are \(s_j\) and \(b\in \mathbb {R}^m\) has coordinates \(r_j\).

A closed convex polyhedral cone is the special case where \(b=0\).

Let \(S\subset \mathbb {R}^n\) be nonempty. We say that \(d\in \mathbb {R}^n\) is a direction tangent to \(S\) at \(x\in S\) when there exists a sequence \(\{ x_k\} \subset S\) and a sequence \(\{ t_k\} \) such that, when \(k\to +\infty \),

The set of all such directions is called the tangent cone (also called the contingent cone, or Bouligand’s cone) to \(S\) at \(x\in S\), denoted by \(T_S(x)\).

Let \(C\) be a nonempty convex set in \(\mathbb {R}^n\). A function \(f : C \to \mathbb {R}\) is said to be convex on \(C\) when, for all pairs \((x,x')\in C\times C\) and all \(\alpha \in [0,1]\), there holds

(The Set \(\operatorname {Conv}\mathbb {R}^n\)) A function \(f:\mathbb {R}^n\to \mathbb {R}\cup \{ +\infty \} \), not identically \(+\infty \), is said to be convex when, for all \((x,x')\in \mathbb {R}^n\times \mathbb {R}^n\) and all \(\alpha \in [0,1]\), there holds

considered as an inequality in \(\mathbb {R}\cup \{ +\infty \} \).

The class of such functions is denoted by \(\operatorname {Conv}\mathbb {R}^n\).

(Domain of a Function) The domain (or also effective domain) of \(f\in \text{Conv }\mathbb {R}^n\) is the nonempty set

(Epigraph of a Function) Given \(f:\mathbb {R}^n\to \mathbb {R}\cup \{ +\infty \} \), not identically equal to \(+\infty \), the epigraph of \(f\) is the nonempty set

Its strict epigraph \(\operatorname {epi}_s f\) is defined likewise, with “\(\ge \)” replaced by “\({\gt}\)” (beware that the word “strict” here has nothing to do with strict convexity).

(Closed Functions) The function \(f:\mathbb {R}^n\to \mathbb {R}\cup \{ +\infty \} \) is said to be closed if it is lower semi-continuous everywhere, or if its epigraph is closed, or if its sublevel-sets are closed.

The closure (or lower semi-continuous hull) of a function \(f\) is the function \(\operatorname {cl}f:\mathbb {R}^n\to \mathbb {R}\cup \{ \pm \infty \} \) defined by:

or equivalently by

(Image Function) Let \(A:\mathbb {R}^m\to \mathbb {R}^n\) be a linear operator and let \(g:\mathbb {R}^m\to \mathbb {R}\cup \{ +\infty \} \). The image of \(g\) under \(A\) is the function \(Ag:\mathbb {R}^n\to \mathbb {R}\cup \{ \pm \infty \} \) defined by

(here as always, \(\inf \varnothing =+\infty \)).

(Marginal Function) Let \(g\in \operatorname {Conv}(\mathbb {R}^n\times \mathbb {R}^m)\). Then

is the marginal function of \(g\).

Let \(g:\mathbb {R}^n\to \mathbb {R}\cup \{ +\infty \} \), not identically \(+\infty \), be minorized by an affine function. The common function \(f_1=f_2=f_3\) of Proposition 2.5.1 is called the convex hull of \(g\), denoted by \(\operatorname {co}g\). The closed convex hull of \(g\) is any of the functions described by Proposition 2.5.2; it is denoted by \(\overline{\operatorname {co}}\, g\) or \(\operatorname {cl}\, \operatorname {co}g\).

(Asymptotic function) The function \(f'_{\infty }\) of Proposition 3.2.1 is called the asymptotic function, or recession function, of \(f\).

(Coercivity) The functions \(f\in \operatorname {Conv}\mathbb {R}^n\) satisfying (i), (ii) or (iii) are called \(0\)-coercive. Equivalently, the \(0\)-coercive functions are those that “increase at infinity”:

and closed convex \(0\)-coercive functions achieve their minimum over \(\mathbb {R}^n\).

An important particular case is when \(f'_\infty (d)=+\infty \) for all \(d\neq 0\), i.e. when \(f'_\infty = \iota _{\{ 0\} }\). It can be seen that this means precisely

(to establish this equivalence, extract a cluster point of \((x_k/\| x_k\| )\), and use the lower semi-continuity of \(f'_\infty \)). In words: at infinity, \(f\) increases to infinity faster than any affine function; such functions are called \(1\)-coercive, or sometimes just coercive.

A function \(\sigma :\mathbb {R}^n\to \mathbb {R}\cup \{ +\infty \} \) is said to be sublinear if it is convex and positively homogeneous (of degree 1): \(\sigma \in \mathrm{Conv}\, \mathbb {R}^n\) and

(Gauge) Let \(C\) be a closed convex set containing the origin. The function \(\gamma _C\) defined by

is called the gauge of \(C\). As usual, we set \(\gamma _C(x):=+\infty \) if \(x\notin \lambda C\) for no \(\lambda {\gt}0\).

( Support Function) Let \(S\) be a nonempty set in \(\mathbb {R}^n\). The function

defined by

is called the support function of \(S\).

(Breadth of a Set) The breadth of a nonempty set \(S\) along \(x\neq 0\) is

a number in \([0,+\infty ]\). It is \(0\) if and only if \(S\) lies entirely in some affine hyperplane orthogonal to \(x\); such a hyperplane is expressed as

which in particular contains \(S\). The intersection of all these hyperplanes is just the affine hull of \(S\).

Let \(C\) be a nonempty closed convex set, with support function \(\sigma \). For given \(d\neq 0\), the set

is called the exposed face of \(C\) associated with \(d\), or the face exposed by \(d\).

(Directional Derivative) The directional derivative of \(f\) at \(x\) in the direction \(d\) is

The subdifferential \(\partial f(x)\) of \(f\) at \(x\) is the nonempty compact convex set of \(\mathbb {R}^n\) whose support function is \(f'(x,\cdot )\), i.e.

A vector \(s\in \partial f(x)\) is called a subgradient of \(f\) at \(x\).

(Subdifferential II) The subdifferential of \(f\) at \(x\) is the set of vectors \(s\in \mathbb {R}^n\) satisfying

A point \(x\) at which \(\partial f(x)\) has more than one element — i.e. at which \(f\) is not differentiable — is called a kink (or corner-point) of \(f\).

(Grünbaum [1960]). Let \(\mathcal{K}\) be a centered convex set, i.e., \(\int _{x\in \mathcal{K}} x\, dx = 0\), then for any \(w\in \mathbb {R}^n\), \(w\neq 0\), one has

Let \(\mathcal{E}_0=\{ x\in \mathbb {R}^n:(x-c_0)^\top H_0^{-1}(x-c_0)\le 1\} \). For any \(w\in \mathbb {R}^n\), \(w\neq 0\), there exists an ellipsoid \(\mathcal{E}\) such that

and

Furthermore for \(n\ge 2\) one can take \(\mathcal{E}=\{ x\in \mathbb {R}^n:(x-c)^\top H^{-1}(x-c)\le 1\} \) where

Let \(f\) be \(\beta \)-smooth and \(\alpha \)-strongly convex on \(\mathbb {R}^n\). Then for all \(x,y\in \mathbb {R}^n\), one has

Let \(f\) be a \(\beta \)-smooth function on \(\mathbb {R}^n\). Then for any \(x,y\in \mathbb {R}^n\), one has

Let \(f\) be such that (3.4) holds true. Then for any \(x,y\in \mathbb {R}^n\), one has

Let \(x,y\in \mathcal{X}\), \(x^{+}=\Pi _{\mathcal{X}}\bigl(x-\tfrac {1}{\beta }\nabla f(x)\bigr)\), and \(g_{\mathcal{X}}(x)=\beta (x-x^{+})\). Then the following holds true:

Let \(x\in \mathcal{X}\cap \mathcal{D}\) and \(y\in \mathcal{D}\), then

which also implies

Let \(x\in \partial C\), where \(C\neq \varnothing \) is convex in \(\mathbb {R}^n\) (naturally \(C\neq \mathbb {R}^n\)). There exists a hyperplane supporting \(C\) at \(x\).

Let \(b,s_1,\dots ,s_m\) be given in \(\mathbb {R}^n\). The set

is contained in the set

if and only if (see Definition 1.4.5 of a conical hull)

Let \(b,s_1,\dots ,s_m\) be given in \(\mathbb {R}^n\). Then exactly one of the following statements is true.

1. ?? has a solution \(\alpha \in \mathbb {R}^n\).

2. \[ \left\{ \begin{aligned} & \langle b,x\rangle {\gt}0,\\ & \langle s_j,x\rangle \le 0\quad \text{for }j=1,\dots ,m \end{aligned} \right. \]

   has a solution \(x\in \mathbb {R}^n\).

Let \(s_1,\dots ,s_m\) be given in \(\mathbb {R}^n\). Then the convex cone

is closed.

Let \(f\in \operatorname {Conv}\mathbb {R}^n\) and suppose there are \(x_0,\ \delta ,\ m\) and \(M\) such that

Then \(f\) is Lipschitzian on \(B(x_0,\delta )\); more precisely: for all \(y\) and \(y'\) in \(B(x_0,\delta )\),

For the convex function \(f:\mathbb {R}^n\to \mathbb {R}\) and the sublevel-set (1.3.1), we have

Let \(f:\mathbb {R}^n\to \mathbb {R}\) be convex and \(x\in \mathbb {R}^n\). For any \(\varepsilon {\gt}0\), there exists \(\delta {\gt}0\) such that \(\| h\| \le \delta \) implies

The subdifferential of \(\varphi \) defined by (2.3.1) is

or, more symbolically:

With the notation (4.4.1), (4.4.2),

Let \(\{ C_j\} _{j\in J}\) be an arbitrary family of convex sets. Then

is convex.

For \(i=1,\dots ,k\), let \(C_i\subset \mathbb {R}^{n_i}\) be convex sets. Then \(C_1\times \cdots \times C_k\) is a convex set of \(\mathbb {R}^{n_1}\times \cdots \times \mathbb {R}^{n_k}\).

Let \(A:\mathbb {R}^n\to \mathbb {R}^m\) be an affine mapping and \(C\) a convex set of \(\mathbb {R}^n\). The image \(A(C)\) of \(C\) under \(A\) is convex in \(\mathbb {R}^m\).

If \(D\) is a convex set of \(\mathbb {R}^m\), the inverse image

is convex in \(\mathbb {R}^n\).

If \(C\) is convex, so are its interior \(\operatorname {int}C\) and its closure \(\overline{C}\).

A set \(C\subset \mathbb {R}^n\) is convex if and only if it contains every convex combination of its elements.

The convex hull can also be described as the set of all convex combinations:

The closed convex hull \(\overline{\operatorname {co}}S\) of Definition 1.4.1 is the closure \(\operatorname {cl}(\operatorname {co}S)\) of the convex hull of \(S\).

Let \(S\) be a nonempty compact set such that \(0\notin \operatorname {co}S\). Then

Let the two convex sets \(C_1\) and \(C_2\) satisfy \(\operatorname {ri}C_1\cap \operatorname {ri}C_2\neq \varnothing \). Then

Let \(A:\mathbb {R}^n\to \mathbb {R}^m\) be an affine mapping and \(C\) a convex set of \(\mathbb {R}^n\). Then

If \(D\) is a convex set of \(\mathbb {R}^m\) satisfying \(A^{-1}(\operatorname {ri}D)\neq \varnothing \), then

The three convex sets \(\operatorname {ri}C\), \(C\) and \(\operatorname {cl}C\) have the same affine hull (and hence the same dimension), the same relative interior and the same closure (and hence the same relative boundary).

The closed convex cone \(C_{\infty }(x)\) does not depend on \(x\in C\).

A closed convex set \(C\) is compact if and only if \(C_\infty =\{ 0\} \).

• If \(\{ C_j\} _{j\in J}\) is a family of closed convex sets having a point in common, then

  \[ \left(\bigcap _{j\in J} C_j\right)_\infty = \bigcap _{j\in J}(C_j)_\infty . \]

• If, for \(j=1,\dots ,m\), \(C_j\) are closed convex sets in \(\mathbb {R}^{n_j}\), then

  \[ (C_1\times \cdots \times C_m)_\infty = (C_1)_\infty \times \cdots \times (C_m)_\infty . \]

• Let \(A:\mathbb {R}^n\to \mathbb {R}^m\) be an affine mapping. If \(C\) is closed convex in \(\mathbb {R}^n\) and \(A(C)\) is closed, then

  \[ A(C_\infty )\subset [A(C)]_\infty . \]

• If \(D\) is closed convex in \(\mathbb {R}^m\) with nonempty inverse image, then

  \[ \bigl[\; A^{-1}(D)\; \bigr]_\infty = A^{-1}(D_\infty ). \]

If \(C\) is compact, then \(\operatorname {ext}C\neq \varnothing \).

Let \(F\) be a face of \(C\). Then any extreme point of \(F\) is an extreme point of \(C\).

An exposed face is a face.

Let \(C\) be convex and compact. For \(s\in \mathbb {R}^n\), there holds

For all \((x_1,x_2)\in \mathbb {R}^n\times \mathbb {R}^n\), there holds

Let \(K\) be a closed convex cone. Then \(y_x = p_K(x)\) if and only if

Let \(S\subset \mathbb {R}^n\) and \(C:=\operatorname {co}S\). Any \(x\in C\cap \operatorname {bd}C\) can be represented as a convex combination of \(n\) elements of \(S\).

Let \(K\) be a convex cone with polar \(K^{\circ }\); then, the polar \(K^{\circ \circ }\) of \(K^{\circ }\) is the closure of \(K\).

A direction \(d\) is tangent to \(S\) at \(x\in S\) if and only if

The tangent cone is closed.

The tangent cone to \(C\) at \(x\) is the closure of the cone generated by \(C-\{ x\} \):

The normal cone is the polar of the tangent cone.

Here, the \(C\)’s are nonempty closed convex sets.

1. For \(x\in C_1\cap C_2\), there holds

   \[ T_{C_1\cap C_2}(x)\subset T_{C_1}(x)\cap T_{C_2}(x) \qquad \text{and}\qquad N_{C_1\cap C_2}(x)\supset N_{C_1}(x)+N_{C_2}(x). \]

2. With \(C_i\subset \mathbb R^{n_i}\), \(i=1,2\) and \((x_1,x_2)\in C_1\times C_2\),

   \[ T_{C_1\times C_2}(x_1,x_2)=T_{C_1}(x_1)\times T_{C_2}(x_2), \qquad N_{C_1\times C_2}(x_1,x_2)=N_{C_1}(x_1)\times N_{C_2}(x_2). \]

3. With an affine mapping \(A(x)=y_0+A_0x\) (\(A_0\) linear) and \(x\in C\),

   \[ T_{A(C)}[A(x)]=\operatorname {cl}[A_0T_C(x)] \qquad \text{and}\qquad N_{A(C)}[A(x)]=A_0^{-*}[N_C(x)]. \]

4. In particular (start from (ii), (iii) and proceed as when proving (1.2.2)):

   \[ T_{C_1+C_2}(x_1+x_2)=\operatorname {cl}[T_{C_1}(x_1)+T_{C_2}(x_2)], \qquad N_{C_1+C_2}(x_1+x_2)=N_{C_1}(x_1)\cap N_{C_2}(x_2). \]

For \(x\in C\) and \(s\in \mathbb {R}^n\), the following properties are equivalent:

1. \(s\in N_C(x)\);

2. \(x\) is in the exposed face \(F_C(s)\): \(\langle s,x\rangle =\max _{y\in C}\langle s,y\rangle \);

3. \(x=p_C(x+s)\).

The function \(f\) is strongly convex on \(C\) with modulus \(c\) if and only if the function \(f-\tfrac {1}{2}c\| \cdot \| ^{2}\) is convex on \(C\).

Let \(f:\mathbb {R}^n\to \mathbb {R}\cup \{ +\infty \} \) be not identically equal to \(+\infty \). The three properties below are equivalent:

1. \(f\) is convex in the sense of Definition 1.1.3;

2. its epigraph is a convex set in \(\mathbb {R}^n\times \mathbb {R}\);

3. its strict epigraph is a convex set in \(\mathbb {R}^n\times \mathbb {R}\).

Let \(f\in \text{Conv }\mathbb {R}^n\). The relative interior of \(\operatorname {epi}f\) is the union over \(x\in \operatorname {ri}\, \operatorname {dom}f\) of the open half-lines with bottom endpoints at \(f(x)\):

For \(f:\mathbb {R}^n\to \mathbb {R}\cup \{ +\infty \} \), the following three properties are equivalent:

1. \(f\) is lower semi-continuous on \(\mathbb {R}^n\);

2. \(\operatorname {epi} f\) is a closed set in \(\mathbb {R}^n\times \mathbb {R}\);

3. the sublevel-sets \(S_r(f)\) are closed (possibly empty) for all \(r\in \mathbb {R}\).

Let \(f\in \operatorname {Conv}\mathbb {R}^n\) and \(x'\in \operatorname {ri}\operatorname {dom}f\). There holds (in \(\mathbb {R}\cup \{ +\infty \} \))

For \(f\in \text{Conv }\mathbb {R}^n\), there holds

Let \(\{ f_j\} _{j\in J}\) be an arbitrary family of convex [resp. closed convex] functions. If there exists \(x_0\) such that \(\sup _{j} f_j(x_0) {\lt} +\infty \), then their pointwise supremum \(f := \sup \{ f_j : j\in J\} \) is in \(\mathrm{Conv}\, \mathbb {R}^n\) [resp. in \(\mathrm{Conv}_\mathrm {cl}\, \mathbb {R}^n\)].

Let \(f\in \operatorname {Conv}\mathbb {R}^n\) [resp. \(\overline{\operatorname {Conv}}\mathbb {R}^n\)] and let \(A\) be an affine mapping from \(\mathbb {R}^m\) to \(\mathbb {R}^n\) such that \(\operatorname {Im}A\cap \operatorname {dom}f\neq \varnothing \). Then the function

is in \(\operatorname {Conv}\mathbb {R}^m\) [resp. \(\overline{\operatorname {Conv}}\mathbb {R}^m\)].

If \(f\in \operatorname {Conv}\mathbb {R}^n\), its perspective \(\tilde f\) is in \(\operatorname {Conv}\mathbb {R}^{n+1}\).

Let \(f\in \operatorname {Conv}\mathbb {R}^n\) and let \(x'\in \operatorname {ri}\text{dom }f\). Then the closure \(\overline{f}\) of its perspective is given as follows:

Let the functions \(f_1\) and \(f_2\) be in \(\operatorname {Conv}\mathbb {R}^n\). Suppose that they have a common affine minorant: for some \((s,b)\in \mathbb {R}^n\times \mathbb {R}\),

Then their infimal convolution is also in \(\operatorname {Conv}\mathbb {R}^n\).

Let \(g:\mathbb {R}^n\to \mathbb {R}\cup \{ +\infty \} \), not identically \(+\infty \), be minorized by some affine function: for some \((s,b)\in \mathbb {R}^n\times \mathbb {R}\),

Then, the following three functions \(f_1, f_2\) and \(f_3\) are convex and coincide on \(\mathbb {R}^n\):

Let \(g\) satisfy the hypotheses of Proposition 2.5.1. Then the three functions below

are closed, convex, and coincide on \(\mathbb {R}^n\) with the closure of the function constructed in Proposition 2.5.1.

For \(f\in \overline{\operatorname {Conv}}\mathbb {R}^n\), the asymptotic cone of \(\operatorname {epi} f\) is the epigraph of the function \(f'_{\infty }\in \overline{\operatorname {Conv}}\mathbb {R}^n\) defined by

where \(x_0\) is arbitrary in \(\operatorname {dom} f\).

A function \(f\in \operatorname {Conv}\mathbb {R}^n\) is Lipschitzian on the whole of \(\mathbb {R}^n\) if and only if \(f'_\infty \) is finite on the whole of \(\mathbb {R}^n\). The best Lipschitz constant for \(f\) is then

For \(f\in \operatorname {Conv}\mathbb {R}^n\) and \(x\in \operatorname {int}\text{dom }f\), the three statements below are equivalent:

1. The function

   \[ \mathbb {R}^n\ni d\mapsto \lim _{t\downarrow 0}\frac{f(x+td)-f(x)}{t} \]

   is linear in \(d\);

2. for some basis of \(\mathbb {R}^n\) in which \(x=(\xi ^1,\dots ,\xi ^n)\), the partial derivatives \(\dfrac {\partial f}{\partial \xi ^i}(x)\) exist at \(x\), for \(i=1,\dots ,n\);

3. \(f\) is differentiable at \(x\).

A function \(\sigma :\mathbb R^n\to \mathbb R\cup \{ +\infty \} \) is sublinear if and only if its epigraph \(\operatorname {epi}\sigma \) is a nonempty convex cone in \(\mathbb R^n\times \mathbb R\).

A function \(\sigma :\mathbb {R}^n\to \mathbb {R}\cup \{ +\infty \} \), not identically equal to \(+\infty \), is sublinear if and only if one of the following two properties holds:

or

Let \(\sigma \) be sublinear. If \(x\in U\), i.e. if

then there holds

If \(\sigma _1\) and \(\sigma _2\) are [closed] sublinear and \(t_1,t_2\) are positive numbers, then \(\sigma := t_1\sigma _1 + t_2\sigma _2\) is [closed] sublinear, if not identically \(+\infty \).

If \(\{ \sigma _j\} _{j\in J}\) is a family of [closed] sublinear functions, then \(\sigma := \sup _{j\in J}\sigma _j\) is [closed] sublinear, if not identically \(+\infty \).

Let \(\{ \sigma _j\} _{j\in J}\) be a family of sublinear functions all minorized by some linear function. Then \(\sigma := \operatorname {co}\big(\inf _{j\in J}\sigma _j\big)\) is sublinear.

Let \(\{ \sigma _j\} _{j\in J}\) be a family of sublinear functions all minorized by some linear function. Then if \(J=\{ 1,\dots ,m\} \) is a finite set, we obtain the infimal convolution

A support function is closed and sublinear.

The support function of \(S\) is finite everywhere if and only if \(S\) is bounded.

For \(S\subset \mathbb {R}^n\) nonempty, there holds \(\sigma _S=\sigma _{\operatorname {cl} S}=\sigma _{\operatorname {co} S}\); whence

Let \(S\) be a nonempty closed convex set in \(\mathbb {R}^n\). Then \(\overline{\operatorname {dom}\sigma _S}\) and the asymptotic cone \(S_\infty \) of \(S\) are mutually polar cones.

For \(x\) in a nonempty closed convex set \(C\), it holds

For a nonempty closed convex set \(C\), it holds

where \(X\) can be indifferently taken as: \(\mathbb {R}^n\setminus \{ 0\} \), the unit sphere \(\widetilde{B}\), or \(\operatorname {dom}\sigma _C\setminus \{ 0\} \).

Let \(B\) and \(B^*\) be defined by (3.2.1) and (3.2.2), where \(\| \cdot \| \) is a norm on \(\mathbb {R}^n\). The support function of \(B\) and the gauge of \(B^*\) are the same function \(\| \cdot \| _* \) defined by

Furthermore, \(\| \cdot \| _*\) is a norm on \(\mathbb {R}^n\). The support function of its unit ball \(B^*\) and the gauge of its supported set \(B\) are the same function \(\| \cdot \| \): there holds

Let \(C\) be a closed convex set containing the origin. Its gauge \(\gamma _C\) is the support function of a closed convex set containing the origin, namely

which defines the polar (set) of \(C\).

Let \(C\) be a nonempty compact convex set having \(0\) in its interior, so that \(C^\circ \) enjoys the same properties. Then, for all \(d\) and \(s\) in \(\mathbb {R}^n\), the following statements are equivalent (the notation (3.2.9) is used)

1. \(H(s)\) is a supporting hyperplane to \(C\) at \(d\);

2. \(H(d)\) is a supporting hyperplane to \(C^\circ \) at \(s\);

3. \(d\in \operatorname {bd}C,\ s\in \operatorname {bd}C^\circ \text{ and }\langle s,d\rangle =1\);

4. \(d\in C,\ s\in C^\circ \text{ and }\langle s,d\rangle =1\).

Let \(A:\mathbb {R}^n\to \mathbb {R}^m\) be a linear operator, with adjoint \(A^*\) (for some scalar product \(\langle \cdot ,\cdot \rangle \) in \(\mathbb {R}^m\)). For \(S\subset \mathbb {R}^n\) nonempty, we have

Let \(A:\mathbb {R}^m\to \mathbb {R}^n\) be a linear operator, with adjoint \(A^*\) (for some scalar product \(\langle \cdot ,\cdot \rangle \) in \(\mathbb {R}^m\)). Let \(\sigma \) be the support function of a nonempty closed convex set \(S\subset \mathbb {R}^m\). If \(\sigma \) is minorized on the inverse image

of each \(d\in \mathbb {R}^n\), then the support function of the set \((A^{-1})^*(S)\) is the closure of the image-function \(A\sigma \).

A convex-compact-valued and locally bounded multifunction \(F:\mathbb {R}^n\longrightarrow 2^{\mathbb {R}^n}\) is outer [resp. inner] semi-continuous at \(x_0\in \operatorname {int}\text{dom }F\) if and only if its support function \(x\mapsto \sigma _{F(x)}(d)\) is upper [resp. lower] semi-continuous at \(x_0\) for all \(d\) of norm \(1\).

For fixed \(x\), the function \(f'(x,\cdot )\) is finite sublinear.

The finite sublinear function \(d\mapsto \sigma (d):=f'(x,d)\) satisfies

1. A vector \(s\in \mathbb {R}^n\) is a subgradient of \(f\) at \(x\) if and only if \((s,-1)\in \mathbb {R}^n\times \mathbb {R}\) is normal to \(\operatorname {epi}f\) at \((x,f(x))\). In other words:

   \[ N_{\operatorname {epi}f}(x,f(x))=\{ (\lambda s,-\lambda ): s\in \partial f(x),\ \lambda \ge 0\} . \]

2. The tangent cone to the set \(\operatorname {epi}f\) at \((x,f(x))\) is the epigraph of the directional-derivative function \(d\mapsto f'(x,d)\):

   \[ T_{\operatorname {epi}f}(x,f(x))=\{ (d,r): r\ge f'(x,d)\} . \]

Let \(g:\mathbb {R}^n\to \mathbb {R}\) be convex and suppose that \(g(x_0){\lt}0\) for some \(x_0\in \mathbb {R}^n\). Then

It follows

Let \(f:\mathbb {R}^n\to \mathbb {R}\) be convex. For all \(x\) and \(d\) in \(\mathbb {R}^n\), we have

The subdifferential mapping is monotone in the sense that, for all \(x_1\) and \(x_2\) in \(\mathbb {R}^n\),

A necessary and sufficient condition for a convex function \(f:\mathbb {R}^n\to \mathbb {R}\) to be strictly convex on a convex set \(C\) is: for all \(x_1,x_2\in C\) with \(x_2\neq x_1\),

or equivalently

Let \(f:\mathbb {R}^n\to \mathbb {R}\) be convex. The graph of its subdifferential mapping is closed in \(\mathbb {R}^n\times \mathbb {R}^n\).

The mapping \(\partial f\) is locally bounded, i.e. the image \(\partial f(B)\) of a bounded set \(B\subset \mathbb {R}^n\) is a bounded set in \(\mathbb {R}^n\).

Let \(x\) and \(d\neq 0\) be given in \(\mathbb {R}^n\). For any sequence \((t_k,s_k,d_k)\subset \mathbb {R}_+^*\times \mathbb {R}^n\times \mathbb {R}^n\) satisfying

and any cluster point \(s\) of \((s_k)\), there holds

There holds for all \(x\in \mathbb {R}^n\)

It follows that the support function of \(\mathrm{epi}\, f\) has the expression

The function \(f\) is assumed to satisfy (1.1.1). The conjugate of the function \(g(x):=f(x)+r\) is \(g^*(s)=f^*(s)-r\).

The function \(f\) is assumed to satisfy (1.1.1). With \(t{\gt}0\), the conjugate of the function \(g(x):=tf(x)\) is \(g^*(s)=t f^*(s/t)\).

The function \(f\) is assumed to satisfy (1.1.1). With \(t\neq 0\), the conjugate of the function \(g(x):=f(tx)\) is \(g^*(s)=f^*(s/t)\).

The function \(f\) is are assumed to satisfy (1.1.1). More generally: if \(A\) is an invertible linear operator, \((f\circ A)^*=f^*\circ (A^{-1})^*\).

The function \(f\) is assumed to satisfy (1.1.1). The conjugate of the function \(g(x):=f(x-x_{0})\) is \(g^{*}(s)=f^{*}(s)+\langle s,x_{0}\rangle \).

The function \(f\) is assumed to satisfy (1.1.1). The conjugate of the function \(g(x):=f(x)+\langle s_{0},x\rangle \) is \(g^{*}(s)=f^{*}(s-s_{0})\).

The functions \(f_j\) appearing below are assumed to satisfy (1.1.1). If \(f_{1}\le f_{2}\), then \(f_{1}^{*}\ge f_{2}^{*}\).

The functions \(f_j\) appearing below are assumed to satisfy (1.1.1). “Convexity” of the conjugation: if \(\mathrm{dom}\, f_{1}\cap \mathrm{dom}\, f_{2}\neq \varnothing \) and \(\alpha \in ]0,1[\),

Let \(f\) satisfy (1.1.1), let \(H\) be a subspace of \(\mathbb {R}^n\), and call \(p_H\) the operator of orthogonal projection onto \(H\). Suppose that there is a point in \(H\) where \(f\) is finite. Then \(f+p_{iH}\) satisfies (1.1.1) and its conjugate is

For \(f\) satisfying (1.1.1), let a subspace \(V\) contain the subspace parallel to \(\operatorname {aff\, dom}f\) and set \(U:=V^{\perp }\). For any \(z\in \operatorname {aff\, dom}f\) and any \(s\in \mathbb {R}^{n}\) decomposed as \(s=s_{U}+s_{V}\), there holds

If \(f\) satisfying (1.1.1) is 1-coercive, then \(f^*(s) {\lt} +\infty \) for all \(s \in \mathbb {R}^n\).

For \(f\) satisfying (1.1.1), the following holds:

1. If \(x_0\in \operatorname {int}\text{dom }f\) then \(f^*-\langle x_0,\cdot \rangle \) is \(0\)-coercive;

2. in particular, if \(f\) is finite over \(\mathbb R^n\), then \(f^*\) is \(1\)-coercive.

For \(f\) satisfying (1.1.1), the following properties hold:

The function \(g\) of (3.2.1) has the conjugate

where \(p_{H}\) is the operator of orthogonal projection onto \(H\) and \((\cdot )^{-}\) is the Moore–Penrose pseudo-inverse.

At each \(s\in \operatorname {co}\{ s_1,\ldots ,s_k\} =\operatorname {dom}f^*\), the conjugate of \(f\) has the value ( \(\Delta _k\) is the unit simplex)

The center of gravity method satisfies

For \(t \ge 2n^2\log (R/r)\) the ellipsoid method satisfies \(\{ c_1,\dots ,c_t\} \cap \mathcal{X}\neq \varnothing \) and

Let \(f\) be \(\alpha \)-strongly convex and \(\beta \)-smooth on \(\mathcal X\). Then projected gradient descent with \(\eta =\frac{1}{\beta }\) satisfies for \(t\ge 0\),

Let \(f\) be \(\beta \)-smooth and \(\alpha \)-strongly convex on \(\mathbb {R}^n\). Then gradient descent with \(\eta =\frac{2}{\alpha +\beta }\) satisfies

Let \(f\) be \(\alpha \)-strongly convex and \(\beta \)-smooth, then Nesterov’s accelerated gradient descent satisfies

Let \(f\) be a convex and \(\beta \)-smooth function, then Nesterov’s accelerated gradient descent satisfies

The projected subgradient descent method with \(\eta = \frac{R}{L\sqrt{t}}\) satisfies

Let \(f\) be convex and \(\beta \)-smooth on \(\mathbb {R}^n\). Then gradient descent with \(\eta =\frac{1}{\beta }\) satisfies

Let \(f\) be convex and \(\beta \)-smooth on \(\mathcal{X}\). Then projected gradient descent with \(\eta =\frac{1}{\beta }\) satisfies

Let \(f\) be a convex and \(\beta \)-smooth function w.r.t. some norm \(\| \cdot \| \), \(R=\sup _{x,y\in \mathcal{X}}\| x-y\| \), and \(\gamma _s=\frac{2}{s+1}\) for \(s\ge 1\). Then for any \(t\ge 2\), one has

Let \(f\) be \(\alpha \)-strongly convex and \(L\)-Lipschitz on \(\mathcal{X}\). Then projected subgradient descent with \(\eta _s=\frac{2}{\alpha (s+1)}\) satisfies

Let \(\Phi \) be a mirror map \(\rho \)-strongly convex on \(\mathcal{X}\cap \mathcal{D}\) w.r.t. \(\| \cdot \| \). Let \(R^2=\sup _{x\in \mathcal{X}\cap \mathcal{D}}\Phi (x)-\Phi (x_1)\), and \(f\) be convex and L-Lipschitz w.r.t. \(\| \cdot \| \). Then mirror descent with \(\eta =\dfrac {R}{L}\sqrt{\dfrac {2\rho }{t}}\) satisfies

Let \(\Phi \) be a mirror map \(\rho \)-strongly convex on \(\mathcal{X}\cap D\) w.r.t. \(\| \cdot \| \). Let \(R^2=\sup _{x\in \mathcal{X}\cap D}\Phi (x)-\Phi (x_1)\), and \(f\) be convex and \(L\)-Lipschitz w.r.t. \(\| \cdot \| \). Then dual averaging with \(\eta =\dfrac {R}{L}\sqrt{\dfrac {\rho }{2t}}\) satisfies

Let \(\Phi \) be a mirror map \(\rho \)-strongly convex on \(\mathcal{X}\cap \mathcal{D}\) w.r.t. \(\| \cdot \| \). Let \(R^{2}=\sup _{x\in \mathcal{X}\cap \mathcal{D}}\Phi (x)-\Phi (x_{1})\), and \(f\) be convex and \(\beta \)-smooth w.r.t. \(\| \cdot \| \). Then mirror prox with \(\eta =\frac{\rho }{\beta }\) satisfies

Assume that \(f\) has a Lipschitz Hessian, that is

Let \(x^*\) be a local minimum of \(f\) with strictly positive Hessian, that is \(\nabla ^2 f(x^*)\succeq \mu I_n\), \(\mu {\gt}0\). Suppose that the initial starting point \(x_0\) of Newton’s method is such that

Then Newton’s method is well-defined and converges to \(x^*\) at a quadratic rate:

Let \(f\) be a standard self-concordant function on \(\mathcal{X}\), and \(x\in \operatorname {int}(\mathcal{X})\) such that \(\lambda _f(x)\le 1/4\), then

Let \(\mathcal X\subset \mathbb R^n\) be a closed convex set with non-empty interior. There exists \(F\) which is a \((c\, n)\)-self-concordant barrier for \(\mathcal X\) (where \(c\) is some universal constant).

The path-following scheme described above satisfies

The function \(f\) is convex and \(\beta \)-smooth, and \(g\) is convex. The rate of convergence of FISTA on \(f+g\) is similar to the one of Nesterov’s accelerated gradient descent on \(f\), more precisely:

The function \(f\) is convex and \(\beta \)-smooth, and \(g\) is convex. With \(\eta =\frac{1}{\beta }\) one has

(C. Carathéodory) Any \(x\in \operatorname {co}S\subset \mathbb {R}^n\) can be represented as a convex combination of \(n+1\) elements of \(S\).

(W. Fenchel and L. Bunt) If \(S\subset \mathbb {R}^n\) has no more than \(n\) connected components (in particular, if \(S\) is connected), then any \(x\in \operatorname {co}S\) can be expressed as a convex combination of \(n\) elements of \(S\).

If \(S\) is bounded [resp. compact], then \(\operatorname {co}S\) is bounded [resp. compact].

If \(C\neq \varnothing \), then \(\operatorname {ri}C\neq \varnothing \). In fact, \(\dim (\operatorname {ri}C)=\dim C\).

(H. Minkowski) Let \(C\) be compact, convex in \(\mathbb {R}^n\). Then \(C\) is the convex hull of its extreme points: \(C=\operatorname {co}(\operatorname {ext}C)\).

A point \(y_x\in C\) is the projection \(p_C(x)\) if and only if

Let \(K\) be a closed convex cone. For the three elements \(x,x_1\) and \(x_2\) in \(\mathbb {R}^n\), the properties below are equivalent:

1. \(x=x_1+x_2\) with \(x_1\in K\), \(x_2\in K^\circ \) and \(\langle x_1,x_2\rangle =0\);

2. \(x_1=\mathrm{p}_K(x)\) and \(x_2=\mathrm{p}_{K^\circ }(x)\).

Let \(C\subset \mathbb {R}^n\) be nonempty closed convex, and let \(x\notin C\). Then there exists \(s\in \mathbb {R}^n\) such that

If the two nonempty convex sets \(C_1\) and \(C_2\) satisfy \(\operatorname {ri}C_1\cap (\operatorname {ri}C_2)=\varnothing \), they can be properly separated.

Let \(\varnothing \neq C\subseteq \mathbb {R}^n\) be convex. The set \(C^*\) defined above is the closure of \(C\).

Let be given \((b,r)\) and \((s_j,\rho _j)\) in \(\mathbb {R}^n\times \mathbb {R}\), where \(j\) varies in an (arbitrary) index set \(J\). Suppose that the system of inequalities

has a solution \(x\in \mathbb {R}^n\) (the system is consistent). Then the following two properties are equivalent:

(i) \(\langle b,x\rangle \le r\) for all \(x\) satisfying (4.3.6);

(ii) \((b,r)\) is in the closed convex conical hull of \(S:=\{ (0,1)\} \cup \{ (s_j,\rho _j)\} _{j\in J}\).

(Inequality of Jensen) Let \(f\in \operatorname {Conv}\mathbb {R}^n\). Then, for all collections \(\{ x_1,\dots ,x_k\} \) of points in \(\text{dom }f\) and all \(\alpha =(\alpha _1,\dots ,\alpha _k)\) in the unit simplex of \(\mathbb {R}^k\), there holds (inequality of Jensen in summation form)

Any \(f\in \operatorname {Conv}\mathbb {R}^n\) is minorized by some affine function. More precisely: for any \(x_0\in \operatorname {ri}\operatorname {dom}f\), there is \(s\) in the subspace parallel to \(\operatorname {aff}\operatorname {dom}f\) such that

The closure of \(f\in \text{Conv }\mathbb {R}^n\) is the supremum of all affine functions minorizing \(f\):

Let \(C\) be a nonempty subset of \(\mathbb {R}^n\times \mathbb {R}\) satisfying ??, and let its lower-bound function \(\ell _C\) be defined by ??.

1. If \(C\) is convex, then \(\ell _C\in \operatorname {Conv}\mathbb {R}^n\);

2. If \(C\) is closed convex, then \(\ell _C\in \overline{\operatorname {Conv}}\mathbb {R}^n\).

Let \(f_1,\dots ,f_m\) be in \(\text{Conv }\mathbb {R}^n\) [resp. in \(\overline{\text{Conv }}\mathbb {R}^n\)], let \(t_1,\dots ,t_m\) be positive numbers, and assume that there is a point where all the \(f_j\)’s are finite. Then the function \(f:=\sum _{j=1}^m t_j f_j\) is in \(\text{Conv }\mathbb {R}^n\) [resp. in \(\overline{\text{Conv }}\mathbb {R}^n\)].

Let \(g\) of Definition 2.4.1 be in \(\mathrm{Conv}\, \mathbb {R}^m\). Assume also that, for all \(x\in \mathbb {R}^n\), \(g\) is bounded below on the inverse image \(A^{-1}(x)=\{ y\in \mathbb {R}^m:Ay=x\} \). Then \(Ag\in \mathrm{Conv}\, \mathbb {R}^n\).

Let (2.4.1) have the following form: \(U=\mathbb {R}^p\); \(\varphi \in \text{Conv }\mathbb {R}^p\); \(X=\mathbb {R}^n\) is equipped with the canonical basis; the mapping \(c\) has its components \(c_j\in \text{Conv }\mathbb {R}^p\) for \(j=1,\dots ,n\). Suppose also that the optimal value is \({\gt}-\infty \) for all \(x\in \mathbb {R}^n\), and that

Then the value function

lies in \(\text{Conv }\mathbb {R}^n\).

Let \(g_1,\dots ,g_m\) be in \(\operatorname {Conv}\mathbb {R}^n\), all minorized by the same affine function. Then the convex hull of their infimum is the function

With \(f\in \operatorname {Conv}\mathbb {R}^n\), let \(S\) be a convex compact subset of \(\operatorname {ri}\text{dom }f\). Then there exists \(L=L(S)\ge 0\) such that

Let the convex functions \(f_k:\mathbb {R}^n\to \mathbb {R}\) converge pointwise for \(k\to +\infty \) to \(f:\mathbb {R}^n\to \mathbb {R}\). Then \(f\) is convex and, for each compact set \(S\), the convergence of \(f_k\) to \(f\) is uniform on \(S\).

1. Let \(f_1,\dots ,f_m\) be \(m\) functions of \(\text{Conv }\mathbb {R}^n\), and \(t_1,\dots ,t_m\) be positive numbers. Assume that there is \(x_0\) at which each \(f_j\) is finite. Then,

   \[ \text{for } f:=\sum _{j=1}^m t_j f_j,\qquad \text{we have } f'_\infty =\sum _{j=1}^m t_j(f_j)'_\infty . \]

2. Let \(\{ f_j\} _{j\in J}\) be a family of functions in \(\text{Conv }\mathbb {R}^n\). Assume that there is \(x_0\) at which \(\sup _{j\in J} f_j(x_0){\lt}+\infty \). Then,

   \[ \text{for } f:=\sup _{j\in J} f_j,\qquad \text{we have } f'_\infty =\sup _{j\in J}(f_j)'_\infty . \]

3. Let \(A:\mathbb {R}^n\to \mathbb {R}^m\) be affine with linear part \(A_0\), and let \(f\in \text{Conv }\mathbb {R}^m\). Assume that \(A(\mathbb {R}^n)\cap \text{dom }f\neq \emptyset \). Then \((f\circ A)'_\infty =f'_\infty \circ A_0\).

Let \(f\) be a function differentiable on an open set \(\Omega \subset \mathbb {R}^n\), and let \(C\) be a convex subset of \(\Omega \). Then

1. \(f\) is convex on \(C\) if and only if

   \[ f(x)\ge f(x_0)+\langle \nabla f(x_0),\, x-x_0\rangle \quad \text{for all }(x_0,x)\in C\times C; \tag {4.1.1} \]

2. \(f\) is strictly convex on \(C\) if and only if strict inequality holds in (4.1.1) whenever \(x\neq x_0\);

3. \(f\) is strongly convex with modulus \(c\) on \(C\) if and only if, for all \((x_0,x)\in C\times C\),

   \[ f(x)\ge f(x_0)+\langle \nabla f(x_0),x-x_0\rangle +\tfrac {1}{2}c\| x-x_0\| ^2. \tag {4.1.2} \]

Let \(f\) be a function differentiable on an open set \(\Omega \subset \mathbb {R}^n\), and let \(C\) be a convex subset of \(\Omega \). Then, \(f\) is convex [resp. strictly convex, resp. strongly convex with modulus \(c\)] on \(C\) if and only if its gradient \(\nabla f\) is monotone [resp. strictly monotone, resp. strongly monotone with modulus \(c\)] on \(C\).

Let \(f\in \operatorname {Conv}\mathbb {R}^n\). The subset of \(\operatorname {int}\operatorname {dom}f\) where \(f\) fails to be differentiable is of zero (Lebesgue) measure.

Let \(f\) be twice differentiable on an open convex set \(\Omega \subset \mathbb {R}^n\). Then

1. \(f\) is convex on \(\Omega \) if and only if \(\nabla ^2 f(x_0)\) is positive semi-definite for all \(x_0\in \Omega \);

2. if \(\nabla ^2 f(x_0)\) is positive definite for all \(x_0\in \Omega \), then \(f\) is strictly convex on \(\Omega \);

3. \(f\) is strongly convex with modulus \(c\) on \(\Omega \) if and only if the smallest eigenvalue of \(\nabla ^2 f(\cdot )\) is minorized by \(c\) on \(\Omega \): for all \(x_0\in \Omega \) and all \(d\in \mathbb {R}^n\),

   \[ \langle \nabla ^2 f(x_0)d,d\rangle \ge c\| d\| ^2. \]

Let \(\sigma \) be sublinear and suppose that there exist \(x_1,\dots ,x_m\) in \(\text{dom }\sigma \) such that

Then \(\sigma \) is linear on the subspace spanned by \(x_1,\dots ,x_m\).

Let \(C\) be a closed convex set containing the origin. Then

1. its gauge \(\gamma _C\) is a nonnegative closed sublinear function;

2. \(\gamma _C\) is finite everywhere if and only if \(0\) lies in the interior of \(C\);

3. \(C_\infty \) being the asymptotic cone of \(C\),

   \[ \{ x\in \mathbb {R}^n:\ \gamma _C(x)\le r\} =rC\quad \text{for all }r{\gt}0, \qquad \{ x\in \mathbb {R}^n:\ \gamma _C(x)=0\} =C_\infty . \]

For \(\sigma _1\) and \(\sigma _2\) in the set \(\Phi \) of sublinear functions that are finite everywhere, define

Then \(\Delta \) is a distance on \(\Phi \).

Let \((\sigma _k)\) be a sequence of finite sublinear functions and let \(\sigma \) be a finite function. Then the following are equivalent when \(k\to +\infty \):

1. \((\sigma _k)\) converges pointwise to \(\sigma \);

2. \((\sigma _k)\) converges to \(\sigma \) uniformly on each compact set of \(\mathbb {R}^n\);

3. \(\Delta (\sigma _k,\sigma )\to 0\).

For the nonempty \(S\subset \mathbb {R}^n\) and its support function \(\sigma _S\), there holds

where the set \(X\) can be indifferently taken as: the whole of \(\mathbb {R}^n\), the unit ball \(B(0,1)\) or its boundary the unit sphere \(\tilde{B}\), or \(\operatorname {dom}\sigma _S\).

Let \(S\) be a nonempty closed convex set in \(\mathbb {R}^n\). Then

1. \(s\in \operatorname {aff}S\) if and only if

   \[ \langle s,d\rangle =\sigma _S(d)\quad \text{for all }d\text{ with }\sigma _S(d)+\sigma _S(-d)=0; \tag {2.2.3} \]

2. \(s\in \operatorname {ri}S\) if and only if

   \[ \langle s,d\rangle {\lt}\sigma _S(d)\quad \text{for all }d\text{ with }\sigma _S(d)+\sigma _S(-d){\gt}0; \tag {2.2.4} \]

3. in particular, \(s\in \operatorname {int}S\) if and only if

   \[ \langle s,d\rangle {\lt}\sigma _S(d)\quad \text{for all }d\neq 0. \tag {2.2.5} \]

Let \(\sigma \) be a closed sublinear function; then there is a linear function minorizing \(\sigma \). In fact, \(\sigma \) is the supremum of the linear functions minorizing it. In other words, \(\sigma \) is the support function of the nonempty closed convex set

Let \(S_1\) and \(S_2\) be nonempty closed convex sets; call \(\sigma _1\) and \(\sigma _2\) their support functions. Then

Let \(\sigma _1\) and \(\sigma _2\) be the support functions of the nonempty closed convex sets \(S_1\) and \(S_2\). If \(t_1\) and \(t_2\) are positive, then

Let \(\{ \sigma _j\} _{j\in J}\) be the support functions of the family of nonempty closed convex sets \(\{ S_j\} _{j\in J}\). Then

Let \(\{ \sigma _j\} _{j\in J}\) be the support functions of the family of closed convex sets \(\{ S_j\} _{j\in J}\). If

then

Let \(S\) and \(S'\) be two nonempty compact convex sets of \(\mathbb {R}^n\). Then

The definitions 1.1.4 and 1.2.1 are equivalent.

Let \(f:\mathbb {R}^n\to \mathbb {R}\) be convex and suppose \(0\notin \partial f(x)\). Then, \(S_{f}(x)\) being the sublevel-set (1.3.1),

Let \(f:\mathbb {R}^n\to \mathbb {R}\) be convex and suppose \(0\notin \partial f(x)\). Then a direction \(d\) is normal to \(S f(x)\) at \(x\) if and only if there is some \(t\ge 0\) and some \(s\in \partial f(x)\) such that \(d=ts\):

For \(f:\mathbb {R}^n\to \mathbb {R}\) convex, the following three properties are equivalent:

1. \(f\) is minimized at \(x\) over \(\mathbb {R}^n\), i.e., \(f(y)\ge f(x)\) for all \(y\in \mathbb {R}^n\);

2. \(0\in \partial f(x)\);

3. \(f'(x,d)\ge 0\) for all \(d\in \mathbb {R}^n\).

Let \(f:\mathbb {R}^n\to \mathbb {R}\) be convex. Given two points \(x\neq y\) in \(\mathbb {R}^n\), there exist \(t\in ]0,1[\) and \(s\in \partial f(x_t)\) such that

In other words,

Let \(f:\mathbb {R}^n\to \mathbb {R}\) be convex. For \(x,y\in \mathbb {R}^n\),

Let \(f_1,f_2\) be two convex functions from \(\mathbb {R}^n\) to \(\mathbb {R}\) and \(t_1,t_2\) be positive. Then

Let \(A:\mathbb {R}^n\to \mathbb {R}^m\) be an affine mapping ( \(Ax = A_0x + b\), with \(A_0\) linear and \(b\in \mathbb {R}^m\)) and let \(g\) be a finite convex function on \(\mathbb {R}^m\). Then

Let \(f\), \(F\) and \(g\) be defined as above. For all \(x\in \mathbb {R}^n\),

Let \(f_1,\dots ,f_m\) be \(m\) convex functions from \(\mathbb {R}^n\) to \(\mathbb {R}\) and define

Denoting by \(I(x) := \{ i : f_i(x) = f(x)\} \) the active index-set, we have

With the notation (4.4.1), (4.4.2), assume that \(J\) is a compact set (in some metric space), on which the functions \(j\mapsto f_j(x)\) are upper semi-continuous for each \(x\in \mathbb {R}^n\). Then

With the notation (4.5.1), (4.5.2), assume \(A\) is surjective. Let \(x\) be such that \(Y(x)\) is nonempty. Then, for arbitrary \(y\in Y(x)\),

(and this set is thus independent of the particular optimal \(y\)).

With the notations (5.3.1), (5.3.2), suppose \(\varphi _{0}\notin H\). A necessary and sufficient condition for \(\bar{x}=(\bar{\xi }^{1},\dots ,\bar{\xi }^{n})\in \mathbb {R}^{n}\) to minimize \(f\) of (5.3.1) is that, for some positive integer \(p\le n+1\), there exist \(p\) points \(t_{1},\dots ,t_{p}\) in \(T\), \(p\) integers \(\varepsilon _{1},\dots ,\varepsilon _{p}\) in \(\{ -1,+1\} \) and \(p\) positive numbers \(\alpha _{1},\dots ,\alpha _{p}\) such that

(or equivalently: \(\displaystyle \sum _{k=1}^{p}\alpha _k\varepsilon _k\psi (t_k)=0\quad \text{for all }\psi \in H\)). \(\square \)

A necessary and sufficient for a convex function \(f:\mathbb {R}^n\to \mathbb {R}\) to be strongly convex with modulus \(c{\gt}0\) on a convex set \(C\) is: for all \(x_1,x_2\) in \(C\),

or equivalently

The subdifferential mapping of a convex function \(f:\mathbb {R}^n\to \mathbb {R}\) is outer semi-continuous at any \(x\in \mathbb {R}^n\), i.e.

Let \((f_k)\) be a sequence of (finite) convex functions converging pointwise to \(f:\mathbb {R}^n\to \mathbb {R}\) and let \((x_k)\) converge to \(x\in \mathbb {R}^n\). For any \(\varepsilon {\gt}0\),

Let \(f:\mathbb {R}^n\to \mathbb {R}\) be convex. With the notation (6.3.1), \(\partial f(x)=\operatorname {co}\gamma f(x)\) for all \(x\in \mathbb {R}^n\).

For \(f\) satisfying (1.1.1), the conjugate \(f^*\) is a closed convex function: \(f^*\in \text{Conv }\mathbb {R}^n\).

For \(f\in \overline{\operatorname {Conv}}\mathbb {R}^n\),

For \(f\) satisfying (1.1.1), the function \(f^{**}\) of (1.3.2) is the pointwise supremum of all the affine functions on \(\mathbb {R}^n\) majorized by \(f\). In other words

For \(f\) satisfying (1.1.1) and \(\partial f\) defined by (1.4.1), \(s\in \partial f(x)\) if and only if

Let \(f\in \operatorname {Conv}\mathbb {R}^n\). Then \(\partial f(x)\neq \varnothing \) whenever \(x\in \operatorname {ri}\text{dom }f\).

If \(f\in \operatorname {Conv}\mathbb {R}^n\), the following equivalences hold:

With the above notation, assume that \(\operatorname {Im}A^* \cap \text{dom }g^* \neq \varnothing \). Then \(Ag\) satisfies (1.1.1) and its conjugate is

Take \(g\in \text{Conv }\mathbb {R}^m\), \(A_0\) linear from \(\mathbb {R}^n\) to \(\mathbb {R}^m\) and consider the affine operator \(A(x):=A_0x+y_0\in \mathbb {R}^m\). Suppose that \(A(\mathbb {R}^n)\cap \text{dom }g\neq \emptyset \). Then \(g\circ A\in \text{Conv }\mathbb {R}^n\) and its conjugate is the closure of the convex function

Take \(g\in \operatorname {Conv}\mathbb {R}^m\), \(A_0\) linear from \(\mathbb {R}^n\) to \(\mathbb {R}^m\) and consider the affine operator \(A(x):=A_0x+y_0\in \mathbb {R}^m\). Make the following assumption:

Then, for every \(s\in \operatorname {dom}(g\circ A_0)^*\), the problem

has at least one optimal solution \(\bar p\) and there holds \((g\circ A)^*(s)=g^*(\bar p)-\langle \bar p,y_0\rangle \).

Let \(g_1,g_2\) be in \(\operatorname {Conv}\mathbb {R}^n\) and assume that \(\operatorname {dom}g_1\cap \operatorname {dom}g_2\neq \varnothing \). The conjugate \((g_1+g_2)^*\) of their sum is the closure of the convex function \(g_1^*\mathbin {\square }g_2^*\).

Let \(g_1,g_2\) be in \(\text{Conv }\mathbb {R}^n\) and assume that

Then \((g_1+g_2)^* = g_1^*\mathbin {\square }g_2^*\) and, for every \(s\in \text{dom }(g_1+g_2)^*\), the problem

has at least one optimal solution \((\bar p,\bar q)\), which therefore satisfies

Let \(\{ f_j\} _{j\in J}\) be a collection of functions satisfying (1.1.1) and having a common affine minorant: \(\sup _{j\in J} f_j^*(s) {\lt} +\infty \) for some \(s\in \mathbb {R}^n\). Then their infimum \(f := \inf _{j\in J} f_j\) satisfies (1.1.1), and its conjugate is the supremum of the \(f_j^*\)’s:

Let \(\{ g_j\} _{j\in J}\) be a collection of functions in \(\text{Conv }\mathbb {R}^n\). If their supremum \(g:=\sup _{j\in J} g_j\) is not identically \(+\infty \), it is in \(\text{Conv }\mathbb {R}^n\), and its conjugate is the closed convex hull of the \(g_j^*\)’s:

With \(f\) and \(g\) defined as above, assume that \(f(\mathbb R^n)\cap \operatorname {int}\operatorname {dom}g\neq \varnothing \). For all \(s\in \operatorname {dom}(g\circ f)^*\), define the function \(\psi _s\in \operatorname {Conv}\mathbb R\) by

Then \((g\circ f)^*(s)=\min _{\alpha \in \mathbb R}\psi _s(\alpha )\).

Let \(f\in \operatorname {Conv}\mathbb {R}^n\) be strictly convex. Then \(\operatorname {int}\text{dom }f^*\neq \varnothing \) and \(f^*\) is continuously differentiable on \(\operatorname {int}\text{dom }f^*\).

Let \(f\in \operatorname {Conv}\mathbb {R}^n\) be differentiable on the set \(\Omega :=\operatorname {int}\operatorname {dom}f\). Then \(f^*\) is strictly convex on each convex subset \(C\subset \nabla f(\Omega )\).

Assume that \(f:\mathbb {R}^n\to \mathbb {R}\) is strongly convex with modulus \(c{\gt}0\) on \(\mathbb {R}^n\): for all \((x_1,x_2)\in \mathbb {R}^n\times \mathbb {R}^n\) and \(\alpha \in ]0,1[\),

Then \(\operatorname {dom} f^*=\mathbb {R}^n\) and \(\nabla f^*\) is Lipschitzian with constant \(1/c\) on \(\mathbb {R}^n\):

Let \(f:\mathbb {R}^n\to \mathbb {R}\) be convex and have a gradient-mapping Lipschitzian with constant \(L{\gt}0\) on \(\mathbb {R}^n\): for all \((x_1,x_2)\in \mathbb {R}^n\times \mathbb {R}^n\),

Then \(f^*\) is strongly convex with modulus \(1/L\) on each convex subset \(C\subset \operatorname {dom}\partial f^*\). In particular, there holds for all \((x_1,x_2)\in \mathbb {R}^n\times \mathbb {R}^n\)