Convex analysis

File:3dpoly.svg

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

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

If $0 \leq r \leq 1$ is real and $x, y \in C$ then $r x + (1 - r) y \in C.$
If $0 < r < 1$ is real and $x, y \in C$ with $x \neq y,$ then $r x + (1 - r) y \in C.$

Image:ConvexFunction.svg

Throughout, $f : X \to [-\infty, \infty]$ will be a map valued in the extended real numbers $[-\infty, \infty] = \mathbb{R} \cup \{ \pm \infty \}$ with a domain $\operatorname{domain} f = X$ that is a convex subset of some vector space.

The map $f : X \to [-\infty, \infty]$ is a {{em|convex function}} if

{{NumBlk|:::| $f( r x + (1 - r) y ) \leq r f(x) + (1 - r) f(y)$ |{{EquationRef|Convexity ≤}}|LnSty=1px dashed black}}

holds for any real $0 < r < 1$ and any $x, y \in X$ with $x \neq y.$ If this remains true of $f$ when the defining inequality ({{EquationNote|Convexity ≤}}) is replaced by the strict inequality

{{NumBlk|:::| $f( r x + (1 - r) y ) < r f(x) + (1 - r) f(y)$ |{{EquationRef|Convexity <}}|LnSty=1px dashed black}}

then $f$ is called {{em|strictly convex}}.

Convex functions are related to convex sets. Specifically, the function $f$ is convex if and only if its Epigraph (mathematics)

Image:Epigraph convex.svg (in green), is a convex set.]]

Image:Grafico 3d x2+xy+y2.png convex function $x^2 + x y + y^2.$ ]]

{{NumBlk|:::| $\operatorname{epi} f := \left\{ (x,r) \in X \times \mathbb{R} ~:~ f(x) \leq r \right\}$ |{{EquationRef|Epigraph def.}}|LnSty=1px dashed black}}

is a convex set.{{sfn|Rockafellar|Wets|2009|pp=1-28}} The epigraphs of extended real-valued functions play a role in convex analysis that is analogous to the role played by graphs of real-valued function in real analysis. Specifically, the epigraph of an extended real-valued function provides geometric intuition that can be used to help formula or prove conjectures.

The domain of a function $f : X \to [-\infty, \infty]$ is denoted by $\operatorname{domain} f$ while its {{em|effective domain}} is the set{{sfn|Rockafellar|Wets|2009|pp=1-28}}

{{NumBlk|:::| $\operatorname{dom} f := \{ x \in X ~:~ f(x) < \infty \}.$ |{{EquationRef|dom f def.}}|LnSty=1px dashed black}}

The function $f : X \to [-\infty, \infty]$ is called {{em|proper}} if $\operatorname{dom} f \neq \varnothing$ and $f(x) > -\infty$ for {{em|all}} $x \in \operatorname{domain} f.$ {{sfn|Rockafellar|Wets|2009|pp=1-28}} Alternatively, this means that there exists some $x$ in the domain of $f$ at which $f(x) \in \mathbb{R}$ and $f$ is also {{em|never}} equal to $-\infty.$ In words, a function is {{em|proper}} if its domain is not empty, it never takes on the value $-\infty,$ and it also is not identically equal to $+\infty.$ If $f : \mathbb{R}^n \to [-\infty, \infty]$ is a proper convex function then there exist some vector $b \in \mathbb{R}^n$ and some $r \in \mathbb{R}$ such that

: $f(x) \geq x \cdot b - r$ {{space|4}}for every $x$

where $x \cdot b$ denotes the dot product of these vectors.

Convex conjugate

The {{em|convex conjugate}} of an extended real-valued function $f : X \to [-\infty, \infty]$ (not necessarily convex) is the function $f^* : X^* \to [-\infty, \infty]$ from the (continuous) dual space $X^*$ of $X,$ and{{sfn|Zălinescu|2002|pp=75-79}}

: $f^*\left(x^*\right) = \sup_{z \in X} \left\{ \left\langle x^*, z \right\rangle - f(z) \right\}$

where the brackets $\left\langle \cdot, \cdot \right\rangle$ denote the canonical duality $\left\langle x^*, z \right\rangle := x^*(z).$ The {{em|biconjugate}} of $f$ is the map $f^{**} = \left( f^* \right)^* : X \to [-\infty, \infty]$ defined by $f^{**}(x) := \sup_{z^* \in X^*} \left\{ \left\langle x, z^* \right\rangle - f\left( z^* \right) \right\}$ for every $x \in X.$

If $\operatorname{Func}(X; Y)$ denotes the set of $Y$ -valued functions on $X,$ then the map $\operatorname{Func}(X; [-\infty, \infty]) \to \operatorname{Func}\left( X^*; [-\infty, \infty] \right)$ defined by $f \mapsto f^*$ is called the {{em|Legendre-Fenchel transform}}.

= Subdifferential set and the Fenchel-Young inequality =

If $f : X \to [-\infty, \infty]$ and $x \in X$ then the {{em|subdifferential set}} is

: $\begin{alignat}{4}
\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\} && (\text{“} z \in X \text{$ } \text{ can be replaced with: } \text{“} z \in X \text{ such that } z \neq x \text{}) \\ &= \left\{ x^* \in X^* ~:~ \left\langle x^*, x \right\rangle - f(x) \geq \left\langle x^*, z \right\rangle - f(z) \text{ for all } z \in X \right\} && \\ &= \left\{ x^* \in X^* ~:~ \left\langle x^*, x \right\rangle - f(x) \geq \sup_{z \in X} \left\langle x^*, z \right\rangle - f(z) \right\} && \text{ The right hand side is } f^*\left( x^* \right) \\ &= \left\{ x^* \in X^* ~:~ \left\langle x^*, x \right\rangle - f(x) = f^*\left( x^* \right) \right\} && \text{ Taking } z := x \text{ in the } \sup{} \text{ gives the inequality } \leq. \\ \end{alignat}

For example, in the important special case where $f = \| \cdot \|$ is a norm on $X$ , it can be shownThe conclusion is immediate if $X = \{ 0 \}$ so assume otherwise. Fix $x \in X.$ Replacing $f$ with the norm gives $\partial f(x) = \left\{ x^* \in X^* ~:~ \left\langle x^*, x \right\rangle - \| x \| \geq \left\langle x^*, z \right\rangle - \| z \| \text{ for all } z \in X \right\}.$ If $x^* \in \partial f(x)$ and $r \geq 0$ is real then using $z := r x$ gives $\left\langle x^*, x \right\rangle - \| x \| \geq \left\langle x^*, r x \right\rangle - \| r x \| = r \left[ \left\langle x^*, x \right\rangle - \| x \| \right],$ where in particular, taking $r := 2$ gives $x^*(x) \geq \| x \|$ while taking $r := \frac1{2}$ gives $x^*(x) \leq \| x \|$ and thus {{nowrap| $x^*(x) = \| x \|$ ;}} moreover, if in addition $x \neq 0$ then because $x^*\left(\frac{x}{\|x\|}\right) = 1,$ it follows from the definition of the dual norm that $\left\| x^* \right\| \geq 1.$ Because $\partial f(x) \subseteq \left\{ x^* \in X^* ~:~ x^*(x) = \| x \| \right\},$ which is equivalent to $\partial f(x) = \partial f(x) \cap \left\{ x^* \in X^* ~:~ x^*(x) = \| x \| \right\},$ it follows that $\partial f(x) = \left\{ x^* \in X^* ~:~ x^*(x) = \| x \| \text{ and } \| z \| \geq \left\langle x^*, z \right\rangle \text{ for all } z \in X \right\},$ which implies $\left\| x^* \right\| \leq 1$ for all $x^* \in \partial f(x).$ From these facts, the conclusion can now be reached. ∎

that if $0 \neq x \in X$ then this definition reduces down to:

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

For any $x \in X$ and $x^* \in X^*,$ $f(x) + f^*\left(x^*\right) \geq \left\langle x^*, x \right\rangle,$ which is called the {{em|Fenchel-Young inequality}}. This inequality is an equality (i.e. $f(x) + f^*\left(x^*\right) = \left\langle x^*, x \right\rangle$ ) if and only if $x^* \in \partial f(x).$ It is in this way that the subdifferential set $\partial f (x)$ is directly related to the convex conjugate $f^*\left( x^* \right).$

= Biconjugate =

The {{em|biconjugate}} of a function $f : X \to [-\infty, \infty]$ is the conjugate of the conjugate, typically written as $f^{**} : X \to [-\infty, \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 {{em|Fenchel–Young inequality}}. For proper functions, $f = f^{**}$ if and only if $f$ is convex and lower semi-continuous by Fenchel–Moreau theorem.{{sfn|Zălinescu|2002|pp=75-79}}

Convex minimization

A {{em|convex minimization}} ({{em|primal}}) {{em|problem}} is one of the form

:find $\inf_{x \in M} f(x)$ when given a convex function $f : X \to [-\infty, \infty]$ and a convex subset $M \subseteq X.$

= Dual problem =

In optimization theory, the {{em|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 [-\infty, \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 [-\infty, \infty]$ be a perturbation function such that $F(x, 0) = f(x).$

The {{em|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{{sfn|Zălinescu|2002|pp=106-113}}

: $\sup_{y^* \in Y^*} -F^*\left(0, y^*\right) \le \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$ ;{{Citation needed|date=January 2012}}
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)$

Notes

{{reflist|30em|refs=

{{cite book|last1=Borwein|first1=Jonathan|last2=Lewis|first2=Adrian|title=Convex Analysis and Nonlinear Optimization: Theory and Examples|edition=2|year=2006|publisher=Springer|isbn=978-0-387-29570-1}}

{{cite book|last1=Borwein|first1=Jonathan|last2=Lewis|first2=Adrian|title=Convex Analysis and Nonlinear Optimization: Theory and Examples|url=https://archive.org/details/convexanalysisno00borw_812|url-access=limited|edition=2|year=2006|publisher=Springer|isbn=978-0-387-29570-1|pages=[https://archive.org/details/convexanalysisno00borw_812/page/n88 76]–77}}

{{cite book|last1=Boţ|first1=Radu Ioan|last2=Wanka|first2=Gert|last3=Grad|first3=Sorin-Mihai|title=Duality in Vector Optimization|year=2009|publisher=Springer|isbn=978-3-642-02885-4}}

{{cite book|last1=Boyd|first1=Stephen|last2=Vandenberghe|first2=Lieven|title=Convex Optimization|publisher=Cambridge University Press|year=2004|isbn=978-0-521-83378-3|url=https://web.stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf|access-date=October 3, 2011}}

{{cite book|last=Csetnek|first=Ernö Robert|title=Overcoming the failure of the classical generalized interior-point regularity conditions in convex optimization. Applications of the duality theory to enlargements of maximal monotone operators|year=2010|publisher=Logos Verlag Berlin GmbH|isbn=978-3-8325-2503-3}}

{{cite book|last=Rockafellar|first=R. Tyrrell|author-link=Rockafellar, R. Tyrrell|title=Convex Analysis|publisher=Princeton University Press|location=Princeton, NJ|year=1997|orig-year=1970|isbn=978-0-691-01586-6}}

}}

References

{{Bauschke Combettes Convex Analysis and Monotone Operator Theory in Hilbert Spaces 2nd ed 2017}}
{{Boyd Vandenberghe Convex Optimization 2004}}
{{cite book|last1=Hiriart-Urruty|first1=J.-B.|author1-link=J.-B. Hiriart-Urruty|last2=Lemaréchal|first2=C.|author2-link=C. Lemaréchal|title=Fundamentals of convex analysis|publisher=Springer-Verlag |location=Berlin |year=2001 |isbn=978-3-540-42205-1}}
{{cite book|last1=Kusraev|first1=A.G.|last2=Kutateladze|first2=Semen Samsonovich|author2-link=Semen Samsonovich Kutateladze|title=Subdifferentials: Theory and Applications|publisher=Kluwer Academic Publishers|year=1995|isbn=978-94-011-0265-0|location=Dordrecht}}
{{Rockafellar Wets Variational Analysis 2009 Springer}}
{{Cite book |last=Rockafellar |first=R. Tyrrell |title=Convex analysis |date=1970 |publisher=Princeton University Press |isbn=978-0-691-08069-7 |series=Princeton mathematical series |location=Princeton, N.J}}
{{Rudin Walter Functional Analysis|edition=2}}
{{cite book|last=Singer|first=Ivan|title=Abstract convex analysis|series=Canadian Mathematical Society series of monographs and advanced texts|publisher=John Wiley & Sons, Inc.|location=New York|year= 1997|pages=xxii+491|isbn=0-471-16015-6|mr=1461544}}
{{cite book|last1=Stoer|first1=J.|last2=Witzgall|first2=C.|title=Convexity and optimization in finite dimensions |volume=1 |publisher=Springer |location=Berlin | year=1970 |isbn=978-0-387-04835-2}}
{{Zălinescu Convex Analysis in General Vector Spaces 2002}}

External links

{{Commons category-inline}}

Analysis