Convex analysis

A 3-dimensional convex polytope. 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 the branch of mathematics devoted to the study of properties of convex functions and convex sets, often with applications in convex minimization, a subdomain of optimization theory.

Convex sets

Main article: Convex set

A subset $C\subseteq X$ of some vector space $X$ is called convex if it satisfies any of the following equivalent conditions:

1. If $0\leq r\leq 1$ is real and $x,y\in C$ then $rx+(1-r)y\in C.$
2. If $0<r<1$ is real and $x,y\in C$ with $x\neq y,$ then $rx+(1-r)y\in C.$
3. $(r+s)C=rC+sC$ for all positive real $r>0$ and $s>0.$

Convex functions

Main article: Convex function

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

$f(\lambda x+(1-\lambda )y)\leq \lambda f(x)+(1-\lambda )f(y).$

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

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

is a convex set.

Convex conjugate

Main article: Convex conjugate

The convex conjugate of an extended real-valued (not necessarily convex) function $f:X\to \mathbb {R} \cup \{\pm \infty \}$ is $f^{*}:X^{*}\to \mathbb {R} \cup \{\pm \infty \}$ where $X^{*}$ is the dual space of $X,$ and

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

Subdifferential set

If $f:X\to \mathbb {R} \cup \{\pm \infty \}$ and $x\in X$ then the subdifferential set is

$\partial f(x)=\left\{x^{*}\in X^{*}~:~f(z)\geq f(x)+\left\langle x^{*},z-x\right\rangle {\text{ for all }}z\in X\right\}.$

For example, if $f=\|\cdot \|$ is a norm on $X$ and if $0\neq x\in X$ then

$\partial f(x)=\left\{x^{*}\in X^{*}~:~\left\langle x^{*},x\right\rangle =\|x\|{\text{ and }}\left\|x^{*}\right\|=1\right\}$     and     $\partial f(0)=\left\{x^{*}\in X^{*}~:~\left\|x^{*}\right\|\leq 1\right\}.$

Biconjugate

The biconjugate of a function $f:X\to \mathbb {R} \cup \{\pm \infty \}$ is the conjugate of the conjugate, typically written as $f^{**}:X\to \mathbb {R} \cup \{\pm \infty \}.$ The biconjugate is useful for showing when strong or weak duality hold (via the perturbation function).

For any $x\in X,$ the inequality $f^{**}(x)\leq f(x)$ follows from the Fenchel–Young inequality. For proper functions, $f=f^{**}$ if and only if $f$ is convex and lower semi-continuous by Fenchel–Moreau theorem. For any $x\in X$ and $x^{*}\in X^{*},$ $f(x)+f^{*}\left(x^{*}\right)\geq \left\langle x^{*},x\right\rangle$ and moreover, $0=f(x)+f^{*}\left(x^{*}\right)-\left\langle x^{*},x\right\rangle$ if and only if $x^{*}\in \partial f(x).$ This characterization follows from the the definition of $\partial f(x),$ because $x^{*}\in \partial f(x)$ if and only if $\left\langle x^{*},z\right\rangle -f(z)\leq \left\langle x^{*},x\right\rangle -f(x)$ for all $z\in X,$ which happens if and only if $\sup _{z\in Z}\left\{\left\langle x^{*},z\right\rangle -f(z)\right\}=\left\langle x^{*},x\right\rangle -f(x),$ where the left hand side is the convex conjugate $f^{*}\left(x^{*}\right).$ It is in this way that the subdifferential set $\partial f(x)$ is directly related to the convex conjugate $f^{*}\left(x^{*}\right).$

Convex minimization

Main article: Convex optimization

A convex minimization (primal) problem is one of the form

find $\inf _{x\in M}f(x)$ when given a convex function $f:X\to \mathbb {R} \cup \{\pm \infty \}$ and a convex subset $M\subseteq X.$

Dual problem

Main article: Duality (optimization)

In optimization theory, the duality principle states that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem.

In general given two dual pairs separated locally convex spaces $\left(X,X^{*}\right)$ and $\left(Y,Y^{*}\right).$ Then given the function $f:X\to \mathbb {R} \cup \{\pm \infty \},$ we can define the primal problem as finding $x$ such that

$\inf _{x\in X}f(x).$

If there are constraint conditions, these can be built into the function $f$ by letting $f=f+I_{\mathrm {constraints} }$ where $I$ is the indicator function. Then let $F:X\times Y\to \mathbb {R} \cup \{\pm \infty \}$ be a perturbation function such that $F(x,0)=f(x).$

The dual problem with respect to the chosen perturbation function is given by

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

where $F^{*}$ is the convex conjugate in both variables of $F.$

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

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

This principle is the same as weak duality. If the two sides are equal to each other, then the problem is said to satisfy strong duality.

There are many conditions for strong duality to hold such as:

• $F=F^{**}$ where $F$ is the perturbation function relating the primal and dual problems and $F^{**}$ is the biconjugate of $F$;
• the primal problem is a linear optimization problem;
• Slater's condition for a convex optimization problem.

Lagrange duality

For a convex minimization problem with inequality constraints,

$\min {}_{x}f(x)$ subject to $g_{i}(x)\leq 0$ for $i=1,\ldots ,m.$

the Lagrangian dual problem is

$\sup {}_{u}\inf {}_{x}L(x,u)$ subject to $u_{i}(x)\geq 0$ for $i=1,\ldots ,m.$

where the objective function $L(x,u)$ is the Lagrange dual function defined as follows:

$L(x,u)=f(x)+\sum _{j=1}^{m}u_{j}g_{j}(x)$

See also

• List of convexity topics
• Werner Fenchel

References

• Bauschke, Heinz H.; Combettes, Patrick L. (28 February 2017). Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Mathematics. Springer Science & Business Media. ISBN 978-3-319-48311-5. OCLC 1037059594.
• Boyd, Stephen; Vandenberghe, Lieven (8 March 2004). Convex Optimization. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge, U.K. New York: Cambridge University Press. ISBN 978-0-521-83378-3. OCLC 53331084.
• Hiriart-Urruty, J.-B.; Lemaréchal, C. (2001). Fundamentals of convex analysis. Berlin: Springer-Verlag. ISBN 978-3-540-42205-1.
• Kusraev, A.G.; Kutateladze, Semen Samsonovich (1995). Subdifferentials: Theory and Applications. Dordrecht: Kluwer Academic Publishers. ISBN 978-94-011-0265-0.
• Rudin, Walter (1991). Functional Analysis. International Series in Pure and Applied Mathematics. Vol. 8 (Second ed.). New York, NY: McGraw-Hill Science/Engineering/Math. ISBN 978-0-07-054236-5. OCLC 21163277.
• Singer, Ivan (1997). Abstract convex analysis. Canadian Mathematical Society series of monographs and advanced texts. New York: John Wiley & Sons, Inc. pp. xxii+491. ISBN 0-471-16015-6. MR 1461544.
• Stoer, J.; Witzgall, C. (1970). Convexity and optimization in finite dimensions. Vol. 1. Berlin: Springer. ISBN 978-0-387-04835-2.
• Zălinescu, Constantin (30 July 2002). Convex Analysis in General Vector Spaces. River Edge, N.J. London: World Scientific Publishing. ISBN 978-981-4488-15-0. MR 1921556. OCLC 285163112 – via Internet Archive.

External links

• Media related to Convex analysis at Wikimedia Commons