View source for Convex analysis

{{Short description|Mathematics of convex functions and sets}}
[[File:3dpoly.svg|thumb|right|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 function]]s and [[convex set]]s, often with applications in [[convex optimization|convex minimization]], a subdomain of [[optimization (mathematics)|optimization theory]].

== Convex sets ==
{{main|Convex set}}

A subset <math>C \subseteq X</math> of some [[vector space]] <math>X</math> is {{em|'''convex'''}} if it satisfies any of the following equivalent conditions:
#If <math>0 \leq r \leq 1</math> is real and <math>x, y \in C</math> then <math>r x + (1 - r) y \in C.</math><ref name="Rockafellar" />
#If <math>0 < r < 1</math> is real and <math>x, y \in C</math> with <math>x \neq y,</math> then <math>r x + (1 - r) y \in C.</math>
[[Image:ConvexFunction.svg|thumb|300px|right|Convex function on an interval.]]
{{main|Convex function}}

Throughout, <math>f : X \to [-\infty, \infty]</math> will be a map valued in the [[Extended real number line|extended real numbers]] <math>[-\infty, \infty] = \mathbb{R} \cup \{ \pm \infty \}</math> with a [[Domain of a function|domain]] <math>\operatorname{domain} f = X</math> that is a convex subset of  some vector space. 
The map <math>f : X \to [-\infty, \infty]</math> is a '''{{em|convex function}}''' if 
{{NumBlk|:::|<math>f( r x + (1 - r) y ) \leq r f(x) + (1 - r) f(y)</math>|{{EquationRef|Convexity ≤}}|LnSty=1px dashed black}}

holds for any real <math>0 < r < 1</math> and any <math>x, y \in X</math> with <math>x \neq y.</math> If this remains true of <math>f</math> when the defining inequality ({{EquationNote|Convexity ≤}}) is replaced by the strict inequality 
{{NumBlk|:::|<math>f( r x + (1 - r) y ) < r f(x) + (1 - r) f(y)</math>|{{EquationRef|Convexity &lt;}}|LnSty=1px dashed black}} 

then <math>f</math> is called '''{{em|strictly convex}}'''.<ref name="Rockafellar" /> 

Convex functions are related to convex sets. Specifically, the function <math>f</math> is convex if and only if its [[Epigraph (mathematics)|'''{{em|epigraph}}''']]
[[Image:Epigraph convex.svg|right|thumb|300px|A function (in black) is convex if and only if its epigraph, which is the region above its [[Graph of a function|graph]] (in green), is a [[convex set]].]]
[[Image:Grafico 3d x2+xy+y2.png|right|300px|thumb|A graph of the [[Polynomial#Number of variables|bivariate]] convex function <math>x^2 + x y + y^2.</math>]]
{{NumBlk|:::|<math>\operatorname{epi} f := \left\{ (x,r) \in X \times \mathbb{R} ~:~ f(x) \leq r \right\}</math>|{{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 [[Graph of a function|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 <math>f : X \to [-\infty, \infty]</math> is denoted by <math>\operatorname{domain} f</math> while its '''{{em|[[effective domain]]}}''' is the set{{sfn|Rockafellar|Wets|2009|pp=1-28}} 
{{NumBlk|:::|<math>\operatorname{dom} f := \{ x \in X ~:~ f(x) < \infty \}.</math>|{{EquationRef|dom ''f'' def.}}|LnSty=1px dashed black}} 

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

where <math>x \cdot b</math> denotes the [[dot product]] of these vectors.

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

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

where the brackets <math>\left\langle \cdot, \cdot \right\rangle</math> denote the [[Dual system|canonical duality]] <math>\left\langle x^*, z \right\rangle := x^*(z).</math> The {{em|'''biconjugate'''}} of <math>f</math> is the map <math>f^{**} = \left( f^* \right)^* : X \to [-\infty, \infty]</math> defined by <math>f^{**}(x) := \sup_{z^* \in X^*} \left\{ \left\langle x, z^* \right\rangle - f\left( z^* \right) \right\}</math> for every <math>x \in X.</math> 
If <math>\operatorname{Func}(X; Y)</math> denotes the set of <math>Y</math>-valued functions on <math>X,</math> then the map <math>\operatorname{Func}(X; [-\infty, \infty]) \to \operatorname{Func}\left( X^*; [-\infty, \infty] \right)</math> defined by <math>f \mapsto f^*</math> is called the {{em|'''Legendre-Fenchel transform'''}}. 

=== Subdifferential set and the Fenchel-Young inequality ===

If <math>f : X \to [-\infty, \infty]</math> and <math>x \in X</math> then the {{em|'''subdifferential set'''}} is

:<math>
\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}
</math>

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

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

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

=== Biconjugate ===

The {{em|'''biconjugate'''}} of a function <math>f : X \to [-\infty, \infty]</math> is the conjugate of the conjugate, typically written as <math>f^{**} : X \to [-\infty, \infty].</math> The biconjugate is useful for showing when [[strong duality|strong]] or [[weak duality]] hold (via the [[perturbation function]]).

For any <math>x \in X,</math> the inequality <math>f^{**}(x) \leq f(x)</math> follows from the {{em|Fenchel–Young inequality}}.  For [[Proper convex function|proper functions]], <math>f = f^{**}</math> [[if and only if]] <math>f</math> is convex and [[lower semi-continuous]] by [[Fenchel–Moreau theorem]].{{sfn|Zălinescu|2002|pp=75-79}}<ref name="BorweinLewis" />

== Convex minimization ==
{{main|Convex optimization}}
A {{em|'''convex minimization'''}} ({{em|primal}}) {{em|problem}} is one of the form

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

=== Dual problem ===
{{main|Duality (optimization)}}
<!-- Copied from [[Duality (optimization)#Duality principle]] -->
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 pair]]s [[separated space|separated]] [[locally convex space]]s <math>\left(X, X^*\right)</math> and <math>\left(Y, Y^*\right).</math> Then given the function <math>f : X \to [-\infty, \infty],</math> we can define the primal problem as finding <math>x</math> such that

:<math>\inf_{x \in X} f(x).</math>

If there are constraint conditions, these can be built into the function <math>f</math> by letting <math>f = f + I_{\mathrm{constraints}}</math> where <math>I</math> is the [[Characteristic function (convex analysis)|indicator function]].  Then let <math>F : X \times Y \to [-\infty, \infty]</math> be a [[perturbation function]] such that <math>F(x, 0) = f(x).</math><ref name="BWG" />

The {{em|dual problem}} with respect to the chosen perturbation function is given by

:<math>\sup_{y^* \in Y^*} -F^*\left(0, y^*\right)</math>

where <math>F^*</math> is the convex conjugate in both variables of <math>F.</math>

The [[duality gap]] is the difference of the right and left hand sides of the inequality{{sfn|Zălinescu|2002|pp=106-113}}<ref name="BWG" /><ref name="Csetnek 2010" />

:<math>\sup_{y^* \in Y^*} -F^*\left(0, y^*\right) \le \inf_{x \in X} F(x, 0).</math>

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:
* <math>F = F^{**}</math> where <math>F</math> is the [[perturbation function]] relating the primal and dual problems and <math>F^{**}</math> is the [[convex conjugate|biconjugate]] of <math>F</math>;{{Citation needed|date=January 2012}}
* the primal problem is a [[linear optimization|linear optimization problem]];
* [[Slater's condition]] for a [[convex optimization|convex optimization problem]].<ref name="borwein" /><ref name="boyd" />

==== Lagrange duality ====
For a convex minimization problem with inequality constraints,

:::<math>\min {}_{x} f(x)</math> subject to <math>g_i(x) \leq 0</math> for <math>i = 1, \ldots, m.</math>

the Lagrangian dual problem is

:::<math>\sup {}_{u} \inf {}_{x} L(x, u)</math> subject to <math>u_i(x) \geq 0</math> for <math>i = 1, \ldots, m.</math>

where the objective function <math>L(x, u)</math> is the Lagrange dual function defined as follows:

:<math>L(x, u) = f(x) + \sum_{j=1}^m u_j g_j(x)</math>

== See also ==

* {{annotated link|Convexity in economics}}
** {{annotated link|Non-convexity (economics)}}
* {{annotated link|List of convexity topics}}
* {{annotated link|Werner Fenchel}}

== Notes ==
{{reflist|30em|refs=

<ref name="borwein">{{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}}</ref>
<ref name="BorweinLewis">{{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}}</ref>
<ref name="BWG">{{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}}</ref>
<ref name="boyd">{{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}}</ref>
<ref name="Csetnek 2010">{{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}}</ref>
<ref name="Rockafellar">{{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}}</ref>

}}

{{reflist|group=proof}}

== References ==

* {{Bauschke Combettes Convex Analysis and Monotone Operator Theory in Hilbert Spaces 2nd ed 2017}} <!-- {{sfn|Bauschke|Combettes|2017|pp=1-2}} -->
* {{Boyd Vandenberghe Convex Optimization 2004}} <!-- {{sfn|Boyd|Vandenberghe|2004|pp=1-2}} -->
* {{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}} <!-- {{sfn|Rockafellar|Wets|2009|p=}} -->
* {{Rudin Walter Functional Analysis|edition=2}} <!-- {{sfn|Rudin|1991|p=}} -->
* {{cite book|last=Singer|first=Ivan|title=Abstract convex analysis|series=Canadian Mathematical Society series of monographs and advanced texts|publisher=John Wiley&nbsp;&&nbsp;Sons, Inc.|location=New&nbsp;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}} <!-- {{sfn|Zălinescu|2002|pp=1-2}} -->

==External links==

* {{Commons category-inline}}

{{Convex analysis and variational analysis}}

[[Category:Convex analysis| ]]
[[Category:Convex geometry|Analysis]]