Convex analysis

Convex sets and convex functions

A subset ${\displaystyle C}$ of a real vector space is convex if, whenever ${\displaystyle x,y\in C}$ and ${\displaystyle 0\le t\le 1}$,

${\displaystyle tx+(1-t)y\in C.}$

This means that the line segment between ${\displaystyle x}$ and ${\displaystyle y}$ lies entirely in ${\displaystyle C}$.

A function ${\displaystyle f:C\to \mathbb{R}}$, where ${\displaystyle C}$ is convex, is convex if

${\displaystyle f(tx+(1-t)y)\le tf(x)+(1-t)f(y)}$

for all ${\displaystyle x,y\in C}$ and all ${\displaystyle 0\le t\le 1}$. It is strictly convex if the inequality is strict whenever ${\displaystyle x\ne y}$ and ${\displaystyle 0<t<1}$, apart from degenerate cases where the two sides are forced to be equal.

A function is convex if and only if its epigraph,

${\displaystyle \mathrm{epi}f=\{(x,r):f(x)\le r\},}$

is a convex set. The epigraph is the region lying on or above the graph of the function. This observation is one reason convex functions and convex sets are studied together: statements about convex functions can often be translated into statements about convex sets in one higher dimension.

For extended-real-valued functions ${\displaystyle f:X\to (-\mathrm{\infty },+\mathrm{\infty }]}$, the effective domain is

${\displaystyle \mathrm{dom}f=\{x\in X:f(x)<+\mathrm{\infty }\}.}$

A function is called proper if its effective domain is nonempty and it never takes the value ${\displaystyle -\mathrm{\infty }}$. Proper convex functions are the usual objects of study in convex analysis.

Finite and infinite dimensions

Convex analysis takes different forms in finite-dimensional and infinite-dimensional spaces. In finite-dimensional Euclidean space, many geometric and topological complications are absent: all norms are equivalent, every linear functional is continuous, and closed and bounded sets are compact. As a result, many results can be stated using ordinary Euclidean topology. For example, a continuous convex function on a closed bounded convex subset of ${\displaystyle {\mathbb{R}}^n}$ attains its minimum, and separation theorems can often be formulated in elementary geometric terms.

In infinite-dimensional spaces, the topology of the underlying vector space becomes part of the theory. The relevant dual space is usually the continuous dual space, and many statements depend on whether one uses the norm topology, a weak topology, or another locally convex topology. Closed and bounded sets need not be compact, linear functionals may fail to be continuous unless continuity is assumed, and convex sets that are large in an algebraic sense may have empty interior in the norm topology.

These differences affect optimization. In finite dimensions, coercivity or compactness hypotheses often ensure the existence of minimizers. In infinite-dimensional spaces, minimizing sequences may fail to have convergent subsequences in the norm topology. Existence results therefore often use weak compactness, lower semicontinuity, and reflexivity assumptions, such as those in the direct methods in the calculus of variations. For example, in a reflexive Banach space, closed bounded convex sets have useful weak compactness properties, making weak lower semicontinuity a standard tool in variational problems.

Interior-point conditions also become more delicate in infinite dimensions. In finite-dimensional convex optimization, conditions such as Slater's condition are often expressed using the ordinary interior or relative interior of a convex set. In infinite-dimensional spaces, many natural convex sets have empty interior, so alternative notions such as algebraic interior, core, quasi-relative interior, or other constraint qualifications may be used.

Duality is similarly affected. The Fenchel–Moreau theorem and related duality theorems require appropriate lower semicontinuity and convexity hypotheses relative to the chosen topology. Thus is closely tied to functional analysis, locally convex spaces, Banach spaces, Hilbert spaces, and monotone operator theory.

Duality

Convex analysis allows many problems to be formulated both in terms of the original vector space and its dual space. For example, a convex set can be described both in terms of its set of points and the set of hyperplanes that meet it. A non-empty closed convex set can also be described by its set of supporting hyperplanes.

For convex functions, duality also plays an important role. Given a proper convex function ${\displaystyle f:X\to \mathbb{R}}$, the supporting hyperplanes of the epigraph are encoded by the convex conjugate, defined at a point ${\displaystyle x^{\ast }\in X^{\ast }}$ by $${\displaystyle f^{\ast }(x^{\ast })=\underset{z\in X}{sup}\left\{⟨x^{\ast },z⟩-f(z)\right\}}$$ where the brackets ${\displaystyle ⟨\cdot ,\cdot ⟩}$ denote the canonical duality ${\displaystyle ⟨x^{\ast },z⟩:=x^{\ast }(z).}$ The function ${\displaystyle f^{\ast }(x^{\ast })}$ makes sense, more generally, regardless of the convexity of ${\displaystyle f}$, but the convex conjugate of any function is always convex.

Geometrically, the convex conjugate describes the supporting affine functions of the epigraph of ${\displaystyle f}$. For a fixed dual vector ${\displaystyle x^{\ast }}$, the value ${\displaystyle f^{\ast }(x^{\ast })}$ is the smallest constant ${\displaystyle c}$ such that the affine function

${\displaystyle x\mapsto ⟨x^{\ast },x⟩-c}$

lies below ${\displaystyle f}$ on its domain. Indeed, the definition of the conjugate is equivalent to

${\displaystyle ⟨x^{\ast },x⟩-f^{\ast }(x^{\ast })\le f(x)}$

for all ${\displaystyle x}$. Hence the hyperplane

${\displaystyle r=⟨x^{\ast },x⟩-f^{\ast }(x^{\ast })}$

lies below the epigraph of ${\displaystyle f}$. If this hyperplane touches the epigraph at ${\displaystyle (x,f(x))}$, then it is a supporting hyperplane there. This touching condition is equivalent to

${\displaystyle f(x)+f^{\ast }(x^{\ast })=⟨x^{\ast },x⟩,}$

or equivalently ${\displaystyle x^{\ast }\in \mathrm{\partial }f(x)}$, the subdifferential of ${\displaystyle f}$ at ${\displaystyle x}$.

Dual problems

Many problems in convex analysis have a corresponding dual problem. In general, the dual problem is formulated on a dual vector space and gives bounds on the value of the original, or primal, problem. Under additional hypotheses these bounds are exact, a property known as strong duality.

A simple geometric example is the relation between a norm and its dual norm. If ${\displaystyle \Vert \cdot \Vert }$ is a norm on ${\displaystyle X}$, its dual norm on ${\displaystyle X^{\ast }}$ is defined by

${\displaystyle \Vert x^{\ast }{\Vert }_{\ast }=\underset{\Vert x\Vert \le 1}{sup}⟨x^{\ast },x⟩.}$

Equivalently, the norm of ${\displaystyle x}$ can be recovered from the dual unit ball:

${\displaystyle \Vert x\Vert =\underset{\Vert x^{\ast }{\Vert }_{\ast }\le 1}{sup}⟨x^{\ast },x⟩.}$

Thus the unit ball of a norm and the unit ball of the dual norm determine one another by polar duality. More generally, if ${\displaystyle C}$ is a convex set containing the origin, its polar set is

${\displaystyle C^{\circ }=\{x^{\ast }\in X^{\ast }:⟨x^{\ast },x⟩\le 1\text{ for all }x\in C\}.}$

Under suitable closedness hypotheses, the bipolar theorem says that ${\displaystyle C}$ can be recovered from its polar by taking the polar again.

A central analytic example is Fenchel duality. Let ${\displaystyle A:X\to Y}$ be a continuous linear map between locally convex spaces, and let ${\displaystyle f:X\to (-\mathrm{\infty },+\mathrm{\infty }]}$ and ${\displaystyle g:Y\to (-\mathrm{\infty },+\mathrm{\infty }]}$ be proper convex functions. The primal problem

${\displaystyle \underset{x\in X}{inf}\{f(x)+g(Ax)\}}$

has the Fenchel dual problem

${\displaystyle \underset{y^{\ast }\in Y^{\ast }}{sup}\{-f^{\ast }(-A^{\ast }{y}^{\ast })-g^{\ast }(y^{\ast })\},}$

where ${\displaystyle A^{\ast }:Y^{\ast }\to X^{\ast }}$ is the adjoint map. The inequality

${\displaystyle \underset{y^{\ast }\in Y^{\ast }}{sup}\{-f^{\ast }(-A^{\ast }{y}^{\ast })-g^{\ast }(y^{\ast })\}\le \underset{x\in X}{inf}\{f(x)+g(Ax)\}}$

is an instance of weak duality. Under standard regularity or constraint qualification assumptions, equality holds.

The usual Lagrange duality of constrained optimization is a special case of this general principle. For a convex optimization problem

${\displaystyle \underset{x}{min}{f}_0(x)\text{subject to}{f}_i(x)\le 0,i=1,\dots ,m,}$

where the functions ${\displaystyle f_i}$ are convex, the Lagrangian is

${\displaystyle L(x,\lambda )=f_0(x)+\sum _{i=1}^m{\lambda }_i{f}_i(x),{\lambda }_i\ge 0.}$

The associated dual function is

${\displaystyle q(\lambda )=\underset{x}{inf}L(x,\lambda ),}$

and the Lagrange dual problem is

${\displaystyle \underset{\lambda \ge 0}{sup}q(\lambda ).}$

Every feasible choice of the multiplier vector ${\displaystyle \lambda }$ gives a lower bound on the primal minimum. When a condition such as Slater's condition holds, the optimal dual value equals the optimal primal value for many finite-dimensional convex programs.

For example, the linear programming problem

${\displaystyle min\{c^{T}x:Ax=b,x\ge 0\}}$

has the dual problem

${\displaystyle max\{b^{T}y:A^{T}y\le c\}.}$

The dual variables ${\displaystyle y}$ may be interpreted as the multipliers attached to the equality constraints ${\displaystyle Ax=b}$.

Duality is especially useful for certifying solutions to optimization problems. If a feasible primal point and a feasible dual point have the same objective value, then both are optimal. In this way, convex duality converts an optimization problem into a pair of mutually checking problems, one in the original space and one in the dual space.

General perturbation formulation

A general way to construct dual problems in convex analysis uses a perturbation function. Let ${\displaystyle X}$ and ${\displaystyle Y}$ be locally convex spaces, and let

${\displaystyle F:X\times Y\to (-\mathrm{\infty },+\mathrm{\infty }]}$

be a proper convex function. The associated value function is

${\displaystyle p(y)=\underset{x\in X}{inf}F(x,y).}$

The original, or primal, problem is the computation of ${\displaystyle p(0)}$, that is,

${\displaystyle \underset{x\in X}{inf}F(x,0).}$

The convex conjugate of ${\displaystyle F}$ is defined on ${\displaystyle X^{\ast }\times Y^{\ast }}$. Since

${\displaystyle p^{\ast }(y^{\ast })=F^{\ast }(0,y^{\ast }),}$

the biconjugate inequality ${\displaystyle p^{\ast \ast }(0)\le p(0)}$ gives the dual problem

${\displaystyle \underset{y^{\ast }\in Y^{\ast }}{sup}-F^{\ast }(0,y^{\ast }).}$

Thus weak duality takes the form

${\displaystyle \underset{y^{\ast }\in Y^{\ast }}{sup}-F^{\ast }(0,y^{\ast })\le \underset{x\in X}{inf}F(x,0).}$

When equality holds, the primal and dual problems are said to satisfy strong duality. Conditions ensuring equality are usually stated as regularity or constraint-qualification hypotheses, such as interior-point conditions in finite-dimensional convex optimization.

This perturbation framework includes many familiar dualities as special cases, including Fenchel duality and Lagrange duality. Different choices of the perturbation function ${\displaystyle F}$ can lead to different dual problems for the same primal optimization problem.

Subgradients

Convex functions need not be differentiable. For example, the absolute value function ${\displaystyle f(x)=|x|}$ is convex but is not differentiable at ${\displaystyle x=0}$. Convex analysis therefore uses a generalized derivative called a subgradient.

Let ${\displaystyle f:X\to (-\mathrm{\infty },+\mathrm{\infty }]}$ be a convex function on a real vector space, and let ${\displaystyle X^{\ast }}$ be a suitable dual space. A functional ${\displaystyle x^{\ast }\in X^{\ast }}$ is a subgradient of ${\displaystyle f}$ at ${\displaystyle x}$ if

${\displaystyle f(z)\ge f(x)+⟨x^{\ast },z-x⟩}$

for all ${\displaystyle z\in X}$. The set of all subgradients at ${\displaystyle x}$ is the subdifferential of ${\displaystyle f}$ at ${\displaystyle x}$, denoted ${\displaystyle \mathrm{\partial }f(x)}$.

Geometrically, a subgradient defines a supporting hyperplane to the epigraph of ${\displaystyle f}$. If ${\displaystyle f}$ is differentiable at ${\displaystyle x}$, then the subdifferential consists of the ordinary derivative. In finite-dimensional Euclidean space this is written

${\displaystyle \mathrm{\partial }f(x)=\{\mathrm{\nabla }f(x)\}.}$

Subgradients give a basic optimality condition. A point ${\displaystyle x}$ minimizes a proper convex function ${\displaystyle f}$ if and only if

${\displaystyle 0\in \mathrm{\partial }f(x).}$

This generalizes the familiar condition ${\displaystyle \mathrm{\nabla }f(x)=0}$ for differentiable functions.

Lower semicontinuity

Convex analysis often studies functions that are lower semi-continuous rather than continuous. A function ${\displaystyle f:X\to (-\mathrm{\infty },+\mathrm{\infty }]}$ is lower semicontinuous if, roughly speaking, its values cannot suddenly jump downward. Equivalently, in a topological vector space, ${\displaystyle f}$ is lower semicontinuous if the sublevel sets

${\displaystyle \{x\in X:f(x)\le a\}}$

are closed for all real numbers ${\displaystyle a}$. For convex functions, lower semicontinuity is also equivalent to closedness of the epigraph:

${\displaystyle \mathrm{epi}f=\{(x,r):f(x)\le r\}.}$

Thus lower semicontinuous convex functions are often called closed convex functions.

Lower semicontinuity is important in optimization because it helps ensure that minimizing limits do not lose the value of the function. If a sequence or net ${\displaystyle x_i}$ converges to ${\displaystyle x}$, lower semicontinuity gives

${\displaystyle f(x)\le \underset{i}{lim inf}f(x_i).}$

This condition is weaker than continuity, but it is often strong enough for existence theorems, especially when combined with compactness or weak compactness assumptions.

The condition also appears in duality. The convex conjugate of any function is convex and lower semicontinuous with respect to the appropriate weak-* topology. The conjugate of the conjugate, or biconjugate, gives the closed convex envelope of the original function. In one common form, the Fenchel–Moreau theorem states that a proper function on a locally convex space satisfies

${\displaystyle f=f^{\ast \ast }}$

if and only if ${\displaystyle f}$ is convex and lower semicontinuous. Equivalently, closed proper convex functions are exactly the functions that can be recovered from their affine minorants.

Applications and related areas

In convex optimization, the objective is to minimize a convex function over a convex set. Convexity ensures that every local minimum is a global minimum, and duality often provides certificates of optimality. Linear programming, quadratic programming, semidefinite programming, and many methods in statistics and machine learning use this framework.

Convex analysis is also connected with convex geometry, which studies convex bodies, polytopes, supporting hyperplanes, mixed volumes, and related geometric inequalities. Classical finite-dimensional results such as Carathéodory's theorem (convex hull), Helly's theorem, and Radon's theorem describe the combinatorial and geometric structure of convex hulls. These theorems are usually regarded as part of convex geometry, but they provide much of the geometric background for convex analysis.

In functional analysis, compact convex sets are studied through their extreme points. The Krein–Milman theorem states that, under suitable hypotheses, a compact convex set in a locally convex space is generated by its extreme points. Choquet theory refines this idea by representing points of compact convex sets as barycenters of probability measures supported on extreme points. This can be viewed as an infinite-dimensional analogue of writing a point of a polytope as a convex combination of its vertices.

Convexity is also used in probability theory. Jensen's inequality compares the value of a convex function at an average with the average of its values. Convex order compares probability measures by testing them against convex functions, and large deviations theory uses the Legendre–Fenchel transform to express rate functions as convex conjugates of logarithmic moment generating functions.

In optimal transport, the Kantorovich formulation of the transport problem is a convex optimization problem over probability measures, and Kantorovich duality is a form of convex duality. For the quadratic cost on Euclidean space, Brenier's theorem relates optimal transport maps to gradients of convex functions, connecting optimal transport with the Monge–Ampère equation.

Several areas use modified notions of convexity adapted to different structures. In the calculus of variations, rank-one convexity, polyconvexity, and quasiconvexity arise in vector-valued variational problems. In metric geometry and optimization on manifolds, geodesic convexity replaces line segments by geodesics. In several complex variables, notions such as pseudoconvexity, holomorphic convexity, polynomial convexity, and plurisubharmonic functions play roles analogous in some respects to convexity in real analysis.