Convex analysis

3-dimensional convex polyhedron. Convex analysis includes not only the study of convex subsets of Euclidean spaces, but also the study of convex functions on abstract spaces.

Convex analysis is a branch of mathematics devoted to the study of the properties of convex functions and convex sets , often having applications in convex programming , a subdomain of optimization theory .

Content

Convex sets

A convex set is a set $C\subseteq X$ ${\ displaystyle C \ subseteq X}$ for some vector space X such that for any $x,y\in C$ ${\ displaystyle x, y \ in C}$ and $\lambda \in [0,1]$ ${\ displaystyle \ lambda \ in [0,1]}$ ^[one]

\lambda x+(1-\lambda )y\in C

{\ displaystyle \ lambda x + (1- \ lambda) y \ in C}

.

Convex function

A convex function is any extended real-valued function $f:X\to \mathbb {R} \cup \{\pm \infty \}$ {\ displaystyle f: X \ to \ mathbb {R} \ cup \ {\ pm \ infty \}} which satisfies Jensen 's inequality , that is, for any $x,y\in X$ ${\ displaystyle x, y \ in X}$ and any $\lambda \in [0,1]$ ${\ displaystyle \ lambda \ in [0,1]}$

f(\lambda x+(1-\lambda )y)\leqslant \lambda f(x)+(1-\lambda )f(y)

{\ displaystyle f (\ lambda x + (1- \ lambda) y) \ leqslant \ lambda f (x) + (1- \ lambda) f (y)}

^[1] .

Equivalently, a convex function is any (extended) real-valued function such that its epigraph

\left\{(x,r)\in X\times \mathbf {R} :f(x)\leqslant r\right\}

{\ displaystyle \ left \ {(x, r) \ in X \ times \ mathbf {R}: f (x) \ leqslant r \ right \}}

is a convex set ^[1] .

Convex Mate

Convex conjugation of an extended real-valued (not necessarily convex) function $f:X\to \mathbb {R} \cup \{\pm \infty \}$ ${\ displaystyle f: X \ to \ mathbb {R} \ cup \ {\ pm \ infty \}}$ Is a function $f^{*}:X^{*}\to \mathbb {R} \cup \{\pm \infty \}$ ${\ displaystyle f ^ {*}: X ^ {*} \ to \ mathbb {R} \ cup \ {\ pm \ infty \}}$ , where X * is the dual space of the space X ^[2] such that

f^{*}(x^{*})=\sup _{x\in X}\left\{\langle x^{*},x\rangle -f(x)\right\}.

{\ displaystyle f ^ {*} (x ^ {*}) = \ sup _ {x \ in X} \ left \ {\ langle x ^ {*}, x \ rangle -f (x) \ right \}. }

Double pairing

Dual pairing function $f:X\to \mathbb {R} \cup \{\pm \infty \}$ ${\ displaystyle f: X \ to \ mathbb {R} \ cup \ {\ pm \ infty \}}$ Is a pairing pairing, which is usually written as $f^{**}:X\to \mathbb {R} \cup \{\pm \infty \}$ ${\ displaystyle f ^ {**}: X \ to \ mathbb {R} \ cup \ {\ pm \ infty \}}$ . Double conjugation is useful when you need to show that strong or is fulfilled (using ).

For anyone $x\in X$ ${\ displaystyle x \ in X}$ inequality $f^{**}(x)\leqslant f(x)$ ${\ displaystyle f ^ {**} (x) \ leqslant f (x)}$ follows from Fenchel's inequality . For f = f ** if and only if f is convex and lower semicontinuous by the Fenchel – Moreau theorem ^[2] ^[3] .

Convex minimization

The (direct) convex programming problem is a problem of the form

\inf _{x\in M}f(x)

{\ displaystyle \ inf _ {x \ in M} f (x)}

such that $f:X\to \mathbb {R} \cup \{\pm \infty \}$ ${\ displaystyle f: X \ to \ mathbb {R} \ cup \ {\ pm \ infty \}}$ is a convex function, and $M\subseteq X$ ${\ displaystyle M \ subseteq X}$ is a convex set.

The dual task

The duality principle in optimization states that optimization problems can be considered from two points of view, as a direct problem or a dual task .

in the general case, given a ^{[4] of} separable locally convex spaces $\left(X,X^{*}\right)$ ${\ displaystyle \ left (X, X ^ {*} \ right)}$ and function $f:X\to \mathbb {R} \cup \{+\infty \}$ ${\ displaystyle f: X \ to \ mathbb {R} \ cup \ {+ \ infty \}}$ , we can define a direct problem as finding such ${\hat {x}}$ ${\ displaystyle {\ hat {x}}}$ , what $f({\hat {x}})=\inf _{x\in X}f(x).\,$ ${\ displaystyle f ({\ hat {x}}) = \ inf _ {x \ in X} f (x). \,}$ In other words, $f({\hat {x}})$ ${\ displaystyle f ({\ hat {x}})}$ Is the infimum (exact lower bound) of the function $f$ ${\ displaystyle f}$ .

If there are restrictions, they can be built into the function $f$ ${\ displaystyle f}$ if put ${\tilde {f}}=f+I_{\mathrm {constraints} }$ ${\ displaystyle {\ tilde {f}} = f + I _ {\ mathrm {constraints}}}$ where $I$ ${\ displaystyle I}$ - . Let now $F:X\times Y\to \mathbb {R} \cup \{+\infty \}$ ${\ displaystyle F: X \ times Y \ to \ mathbb {R} \ cup \ {+ \ infty \}}$ (for another dual pair $\left(Y,Y^{*}\right)$ ${\ displaystyle \ left (Y, Y ^ {*} \ right)}$ ) is a such that $F(x,0)={\tilde {f}}(x)$ ${\ displaystyle F (x, 0) = {\ tilde {f}} (x)}$ ^[5] .

The dual problem for this perturbation function with respect to the selected problem is defined as

\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})

{\ displaystyle \ sup _ {y ^ {*} \ in Y ^ {*}} - F ^ {*} (0, y ^ {*})}

where F * is the convex conjugation in both variables of the function F.

The duality gap is the difference between the right and left sides of the inequality

\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leqslant \inf _{x\in X}F(x,0),\,

{\ displaystyle \ sup _ {y ^ {*} \ in Y ^ {*}} - F ^ {*} (0, y ^ {*}) \ leqslant \ inf _ {x \ in X} F (x, 0), \,}

Where $F^{*}$ ${\ displaystyle F ^ {*}}$ Is the convex conjugation of both variables, and $\sup$ ${\ displaystyle \ sup}$ means supremum (exact upper bound) ^[6] ^[7] ^[5] ^[6] .

\sup _{y^{*}\in Y^{*}}-F^{*}(0,y^{*})\leqslant \inf _{x\in X}F(x,0).

{\ displaystyle \ sup _ {y ^ {*} \ in Y ^ {*}} - F ^ {*} (0, y ^ {*}) \ leqslant \ inf _ {x \ in X} F (x, 0).}

This principle is the same as . If both sides are equal, they say that the problem satisfies the conditions of strong duality .

There are many conditions for strong duality, such as:

F = F ** , where F is the for the direct and dual problems, and F ** is the double conjugation of the function F ;
a direct task is a linear programming task ;
Slater condition for convex programming problems ^[8] ^[9] .

Lagrange Duality

For a convex minimization problem with inequality constraints

\min _{x}f(x)

{\ displaystyle \ min _ {x} f (x)}

under conditions

g_{i}(x)\leqslant 0

{\ displaystyle g_ {i} (x) \ leqslant 0}

for i = 1, ..., m .

the dual task of Lagrange will be

\sup _{u}\inf _{x}L(x,u)

{\ displaystyle \ sup _ {u} \ inf _ {x} L (x, u)}