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

Script error: No such module "Labelled list hatnote".

A subset $C \subseteq X$ of some vector space $X$ is Template:Em 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 .$ ^[1]
If $0 < r < 1$ is real and $x, y \in C$ with $x \neq y,$ then $r x + (1 - r) y \in C .$

File:ConvexFunction.svg

Convex function on an interval.

Script error: No such module "Labelled list hatnote".

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

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 (Convexity ≤) is replaced by the strict inequality Template:NumBlk

then $f$ is called Template:Em.^[1]

Convex functions are related to convex sets. Specifically, the function $f$ is convex if and only if its [[Epigraph (mathematics)|Template:Em]]

File:Epigraph convex.svg

A function (in black) is convex if and only if its epigraph, which is the region above its graph (in green), is a convex set.

File:Grafico 3d x2+xy+y2.png

A graph of the bivariate convex function

x^{2} + x y + y^{2} .

Template:NumBlk is a convex set.Script error: No such module "Footnotes".Script error: No such module "Check for unknown parameters". 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 $domain f$ while its Template:Em is the setScript error: No such module "Footnotes".Script error: No such module "Check for unknown parameters". Template:NumBlk

The function $f : X \to [- \infty, \infty]$ is called Template:Em if $dom f \neq \emptyset$ and $f (x) > - \infty$ for Template:Em $x \in domain f .$ Script error: No such module "Footnotes".Script error: No such module "Check for unknown parameters". Alternatively, this means that there exists some $x$ in the domain of $f$ at which $f (x) \in ℝ$ and $f$ is also Template:Em equal to $- \infty .$ In words, a function is Template:Em if its domain is not empty, it never takes on the value $- \infty,$ and it also is not identically equal to $+ \infty .$ If $f : ℝ^{n} \to [- \infty, \infty]$ is a proper convex function then there exist some vector $b \in ℝ^{n}$ and some $r \in ℝ$ such that

f (x) \geq x \cdot b - r

Script error: No such module "String".for every

x

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

Convex conjugate

Script error: No such module "Labelled list hatnote". The Template:Em 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,$ andScript error: No such module "Footnotes".Script error: No such module "Check for unknown parameters".

f^{*} (x^{*}) = \sup_{z \in X} {⟨ x^{*}, z ⟩ - f (z)}

where the brackets $⟨ \cdot, \cdot ⟩$ denote the canonical duality $⟨ x^{*}, z ⟩ : = x^{*} (z) .$ If $Func (X; Y)$ denotes the set of $Y$ -valued functions on $X,$ then the map $Func (X; [- \infty, \infty]) \to Func (X^{*}; [- \infty, \infty])$ defined by $f \mapsto f^{*}$ is called the Template:Em.

Subdifferential set and the Fenchel-Young inequality

If $f : X \to [- \infty, \infty]$ and $x \in X$ then the Template:Em is

\begin{aligned} \partial f (x) : & = {x^{*} \in X^{*} : f (z) \geq f (x) + ⟨ x^{*}, z - x ⟩ for all z \in X} & (“ z \in X'' can be replaced with: “ z \in X such that z \neq x'') \\ = {x^{*} \in X^{*} : ⟨ x^{*}, x ⟩ - f (x) \geq ⟨ x^{*}, z ⟩ - f (z) for all z \in X} \\ = {x^{*} \in X^{*} : ⟨ x^{*}, x ⟩ - f (x) \geq \sup_{z \in X} ⟨ x^{*}, z ⟩ - f (z)} & The right hand side is f^{*} (x^{*}) \\ = {x^{*} \in X^{*} : ⟨ x^{*}, x ⟩ - f (x) = f^{*} (x^{*})} & Taking z : = x in the \sup gives the inequality \leq . \end{aligned}

For example, in the important special case where $f = ‖ \cdot ‖$ is a norm on $X$ , it can be shown^{[proof 1]} that if $0 \neq x \in X$ then this definition reduces down to:

\partial f (x) = {x^{*} \in X^{*} : ⟨ x^{*}, x ⟩ = ‖ x ‖ and ‖ x^{*} ‖ = 1}

Script error: No such module "String".andScript error: No such module "String".

\partial f (0) = {x^{*} \in X^{*} : ‖ x^{*} ‖ \leq 1} .

For any $x \in X$ and $x^{*} \in X^{*},$ $f (x) + f^{*} (x^{*}) \geq ⟨ x^{*}, x ⟩,$ which is called the Template:Em. This inequality is an equality (i.e. $f (x) + f^{*} (x^{*}) = ⟨ x^{*}, x ⟩$ ) 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^{*} (x^{*}) .$

Biconjugate

The Template:Em of a function $f : X \to [- \infty, \infty]$ , typically written as $f^{* *} : X \to [- \infty, \infty]$ , is the conjugate of the conjugate; $f^{* *} (x) : = \sup_{z^{*} \in X^{*}} {⟨ x, z^{*} ⟩ - f^{*} (z^{*})}$ for every $x \in X$ . 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 Template:Em. For proper functions, $f = f^{* *}$ if and only if $f$ is convex and lower semi-continuous by Fenchel–Moreau theorem.Script error: No such module "Footnotes".Script error: No such module "Check for unknown parameters".^[2]

Convex minimization

Script error: No such module "Labelled list hatnote". A Template:Em (Template:Em) Template:Em 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

Script error: No such module "Labelled list hatnote". In optimization theory, the Template:Em 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 $(X, X^{*})$ and $(Y, Y^{*}) .$ 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_{c o n s t r a i n t s}$ 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) .$ ^[3]

The Template:Em with respect to the chosen perturbation function is given by

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

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 inequalityScript error: No such module "Footnotes".Script error: No such module "Check for unknown parameters".^[3]^[4]

\sup_{y^{*} \in Y^{*}} - F^{*} (0, y^{*}) \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$ ;Script error: No such module "Unsubst".
the primal problem is a linear optimization problem;
Slater's condition for a convex optimization problem.^[5]^[6]

Lagrange duality

For a convex minimization problem with inequality constraints,

\min_{x} f (x)

subject to

g_{i} (x) \leq 0

for

i = 1, \dots, m .

the Lagrangian dual problem is

\sup_{u} \inf_{x} L (x, u)

subject to

u_{i} (x) \geq 0

for

i = 1, \dots, 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

↑ ^a ^b Script error: No such module "citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ ^a ^b Script error: No such module "citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ Script error: No such module "citation/CS1".
↑ Script error: No such module "citation/CS1".

Script error: No such module "Check for unknown parameters". <templatestyles src="Reflist/styles.css" />

↑ The conclusion is immediate if $X = {0}$ so assume otherwise. Fix $x \in X .$ Replacing $f$ with the norm gives $\partial f (x) = {x^{*} \in X^{*} : ⟨ x^{*}, x ⟩ - ‖ x ‖ \geq ⟨ x^{*}, z ⟩ - ‖ z ‖ for all z \in X} .$ If $x^{*} \in \partial f (x)$ and $r \geq 0$ is real then using $z : = r x$ gives $⟨ x^{*}, x ⟩ - ‖ x ‖ \geq ⟨ x^{*}, r x ⟩ - ‖ r x ‖ = r [⟨ x^{*}, x ⟩ - ‖ x ‖],$ where in particular, taking $r : = 2$ gives $x^{*} (x) \geq ‖ x ‖$ while taking $r : = \frac{1}{2}$ gives $x^{*} (x) \leq ‖ x ‖$ and thus $x^{*} (x) = ‖ x ‖$ ; moreover, if in addition $x \neq 0$ then because $x^{*} (\frac{x}{‖ x ‖}) = 1,$ it follows from the definition of the dual norm that $‖ x^{*} ‖ \geq 1 .$ Because $\partial f (x) \subseteq {x^{*} \in X^{*} : x^{*} (x) = ‖ x ‖},$ which is equivalent to $\partial f (x) = \partial f (x) \cap {x^{*} \in X^{*} : x^{*} (x) = ‖ x ‖},$ it follows that $\partial f (x) = {x^{*} \in X^{*} : x^{*} (x) = ‖ x ‖ and ‖ z ‖ \geq ⟨ x^{*}, z ⟩ for all z \in X},$ which implies $‖ x^{*} ‖ \leq 1$ for all $x^{*} \in \partial f (x) .$ From these facts, the conclusion can now be reached. ∎

Script error: No such module "Check for unknown parameters".

References

Template:Bauschke Combettes Convex Analysis and Monotone Operator Theory in Hilbert Spaces 2nd ed 2017
Template:Boyd Vandenberghe Convex Optimization 2004
Script error: No such module "citation/CS1".
Script error: No such module "citation/CS1".
Template:Rockafellar Wets Variational Analysis 2009 Springer
Script error: No such module "citation/CS1".
Template:Rudin Walter Functional Analysis
Script error: No such module "citation/CS1".
Script error: No such module "citation/CS1".
Template:Zălinescu Convex Analysis in General Vector Spaces 2002

External links

Template:Sister-inline

Template:Convex analysis and variational analysis

[Rockafellar-1] Script error: No such module "citation/CS1".

[BorweinLewis-3] Script error: No such module "citation/CS1".

[BWG-4] Script error: No such module "citation/CS1".

[Csetnek_2010-5] Script error: No such module "citation/CS1".

[borwein-6] Script error: No such module "citation/CS1".

[boyd-7] Script error: No such module "citation/CS1".

[2] The conclusion is immediate if $X = {0}$ so assume otherwise. Fix $x \in X .$ Replacing $f$ with the norm gives $\partial f (x) = {x^{*} \in X^{*} : ⟨ x^{*}, x ⟩ - ‖ x ‖ \geq ⟨ x^{*}, z ⟩ - ‖ z ‖ for all z \in X} .$ If $x^{*} \in \partial f (x)$ and $r \geq 0$ is real then using $z : = r x$ gives $⟨ x^{*}, x ⟩ - ‖ x ‖ \geq ⟨ x^{*}, r x ⟩ - ‖ r x ‖ = r [⟨ x^{*}, x ⟩ - ‖ x ‖],$ where in particular, taking $r : = 2$ gives $x^{*} (x) \geq ‖ x ‖$ while taking $r : = \frac{1}{2}$ gives $x^{*} (x) \leq ‖ x ‖$ and thus $x^{*} (x) = ‖ x ‖$ ; moreover, if in addition $x \neq 0$ then because $x^{*} (\frac{x}{‖ x ‖}) = 1,$ it follows from the definition of the dual norm that $‖ x^{*} ‖ \geq 1 .$ Because $\partial f (x) \subseteq {x^{*} \in X^{*} : x^{*} (x) = ‖ x ‖},$ which is equivalent to $\partial f (x) = \partial f (x) \cap {x^{*} \in X^{*} : x^{*} (x) = ‖ x ‖},$ it follows that $\partial f (x) = {x^{*} \in X^{*} : x^{*} (x) = ‖ x ‖ and ‖ z ‖ \geq ⟨ x^{*}, z ⟩ for all z \in X},$ which implies $‖ x^{*} ‖ \leq 1$ for all $x^{*} \in \partial f (x) .$ From these facts, the conclusion can now be reached. ∎

[1]

[proof 1]

[2]

[3]

[4]

[5]

[6]

Convex analysis

Contents

Convex sets

Convex conjugate

Subdifferential set and the Fenchel-Young inequality

Biconjugate

Convex minimization

Dual problem

Lagrange duality

See also

Notes

References

External links

Navigation menu

Convex analysis

Convex sets

Convex conjugate

Subdifferential set and the Fenchel-Young inequality

Biconjugate

Convex minimization

Dual problem

Lagrange duality

See also

Notes

References

External links

Navigation menu

Search