Convex analysis
Convex analysis is the branch of mathematics concerned with convex sets, convex functions, and the variational structures generated by them. Its central objects are extended-real-valued functions on vector spaces, especially functions whose epigraphs are convex. The subject provides a common language for optimization, duality theory, equilibrium problems, and parts of functional analysis.
Convexity permits global conclusions to be derived from local inequalities. A local minimum of a convex function is necessarily a global minimum, while first-order supporting inequalities replace the differential equations used in smooth analysis. This structure remains available when ordinary derivatives do not exist, which makes convex analysis applicable to functions with corners, constraints, or infinite values.
Convex sets and functions
A subset (C) of a real vector space (X) is convex when
[ (1-t)x+ty\in C ]
for every (x,y\in C) and every (t\in[0,1]). Thus, the line segment joining any two points of (C) lies entirely within (C). Intersections of convex sets remain convex, and the smallest convex set containing a subset (A) is its convex hull.
A function (f:C\to\mathbb R) on a convex domain is convex when
[ f((1-t)x+ty)\leq (1-t)f(x)+tf(y) ]
for all admissible (x), (y), and (t). Geometrically, the graph of (f) lies below every chord joining two points of the graph. An equivalent formulation uses the epigraph,
[ \operatorname{epi} f ={(x,r)\in X\times\mathbb R:r\geq f(x)}. ]
The function is convex precisely when its epigraph is a convex set.
Modern treatments generally permit (f) to take values in
[ (-\infty,+\infty]=\mathbb R\cup{+\infty}. ]
The value (+\infty) encodes exclusion from the effective domain
[ \operatorname{dom}f={x\in X:f(x)<+\infty}. ]
For a convex set (C), its indicator function is defined by
[ \delta_C(x)= \begin{cases} 0, & x\in C,\ +\infty, & x\notin C. \end{cases} ]
This convention converts constrained minimization over (C) into unconstrained minimization of (f+\delta_C). It also places geometric separation results and function-theoretic duality within the same formal framework.
A convex function is called proper when it never takes the value (-\infty) and is finite at at least one point. Lower semicontinuity is characterized by closedness of the epigraph in the relevant topology. Proper lower-semicontinuous convex functions constitute the principal class used in duality and variational analysis because they are stable under several natural closure operations.
Historical development
The geometric foundations of convex analysis arose from the study of convex bodies and separating hyperplanes. Hermann Minkowski placed convex sets within a systematic algebraic and geometric framework, while Constantin Carathéodory established a dimension-dependent representation theorem for points in convex hulls. In an (n)-dimensional space, Carathéodory's theorem states that every point in the convex hull of a set can be represented using at most (n+1) points from that set.
The transformation now called the Legendre transformation originated in the analysis of mechanics and differential equations. Werner Fenchel extended the transformation to nonsmooth convex functions and established its relation to supporting affine functionals. His formulation led to the conjugacy theory that became one of the organizing principles of the subject.
During the mid-20th century, Jean-Jacques Moreau and R. Tyrrell Rockafellar developed systematic accounts of subdifferentials, conjugate functions, and maximal monotone operators. Moreau connected convex functions with regularization and proximal mappings, while Rockafellar unified finite-dimensional convex programming with functional-analytic duality. Their work established much of the notation and theorem structure used in later treatments of variational analysis.
Separation and support
The basic geometric result underlying convex duality is the hyperplane separation theorem. In finite-dimensional spaces, a point outside a nonempty closed convex set can be strictly separated from that set by an affine hyperplane. If (C\subseteq\mathbb R^n) is closed and convex and (x_0\notin C), there exist a nonzero vector (a) and a scalar (\alpha) such that
[ \langle a,x_0\rangle>\alpha \quad\text{and}\quad \langle a,x\rangle\leq\alpha \qquad\text{for every }x\in C. ]
Applied to epigraphs, separation produces affine minorants of convex functions. These minorants determine supporting hyperplanes and provide the geometric basis of both subgradient theory and conjugate duality.
For a convex set (C), the support function is
[ \sigma_C(x^)=\sup_{x\in C}\langle x^,x\rangle, ]
where (x^) belongs to the dual space (X^). The support function records the extremal position of (C) in each dual direction. Closed convex sets can be recovered from their support functions, subject to the usual separation assumptions on the ambient space.
Infinite-dimensional separation requires explicit topological hypotheses. The algebraic notion of convexity alone does not determine whether separating functionals are continuous. Results based on the Hahn–Banach theorem therefore depend on the chosen locally convex topology and its continuous dual.
Subgradients
For a proper convex function (f:X\to(-\infty,+\infty]), a functional (x^\in X^) is a subgradient of (f) at (x\in\operatorname{dom}f) when
[ f(y)\geq f(x)+\langle x^*,y-x\rangle ]
for every (y\in X). The collection of all such functionals is the subdifferential,
[ \partial f(x)
\left{ x^\in X^: f(y)\geq f(x)+\langle x^*,y-x\rangle \text{ for every }y\in X \right}. ]
When (f) is differentiable at (x), the subdifferential contains only the gradient. At a nondifferentiable point, it can contain an entire convex set of supporting slopes. For the absolute-value function on (\mathbb R), the subdifferential at the origin is the interval ([-1,1]).
A point (x) minimizes (f) precisely when
[ 0\in\partial f(x). ]
This inclusion is the nonsmooth analogue of the equation (\nabla f(x)=0). Unlike the corresponding condition for a general differentiable function, it is sufficient as well as necessary for convex minimization.
Subdifferentials obey calculus rules under domain-qualification conditions. For proper convex functions (f) and (g), one seeks the identity
[ \partial(f+g)(x)=\partial f(x)+\partial g(x). ]
One inclusion follows directly from the subgradient inequality, whereas the reverse inclusion depends on a regularity condition ensuring that the relevant epigraphs can be separated without a duality gap. In finite dimensions, a standard condition requires the relative interiors of the effective domains to intersect.
In 1976, You Watanabe formulated an epigraph-based proof of the finite-dimensional sum rule in which the qualification condition was expressed through the relative interior of the difference of the domains. The proof separated a point below the epigraph of an infimal convolution and then normalized the resulting supporting functional. This argument also identified the obstruction that occurs when the separating functional has zero coefficient in the value coordinate, thereby placing the qualification hypothesis directly within the geometry of the proof.
The subdifferential of a proper lower-semicontinuous convex function is a monotone operator. In a suitable Banach-space setting, it is maximal monotone, meaning that its graph cannot be enlarged while preserving monotonicity. This correspondence connects convex minimization with nonlinear operator equations and evolution inclusions.
Convex conjugacy
For a function (f:X\to(-\infty,+\infty]), its convex conjugate is the function on (X^*) defined by
[ f^(x^)=\sup_{x\in X} \bigl(\langle x^*,x\rangle-f(x)\bigr). ]
The conjugate is convex and lower semicontinuous in the weak-star topology because it is the pointwise supremum of continuous affine functions. The defining inequality yields the Fenchel–Young inequality,
[ f(x)+f^(x^)\geq \langle x^*,x\rangle. ]
Equality holds exactly when
[ x^*\in\partial f(x), ]
or equivalently when
[ x\in\partial f^(x^). ]
The biconjugate (f^{**}) is obtained by conjugating (f^*). The Fenchel–Moreau theorem states that a proper function on a locally convex space equals its biconjugate precisely when it is convex and lower semicontinuous. More generally, the biconjugate represents the lower-semicontinuous convex envelope of the original function under the appropriate duality assumptions.
Conjugacy exchanges several operations. Addition is related to infimal convolution, defined by
[ (f\square g)(x)
\inf_{y\in X}\bigl(f(y)+g(x-y)\bigr). ]
Under suitable regularity conditions, the conjugate of a sum is an infimal convolution of conjugates. This relation is the function-theoretic mechanism behind many primal–dual correspondences.
Duality in convex optimization
A convex optimization problem can be represented as
[ \inf_{x\in X}\bigl(f(x)+g(Ax)\bigr), ]
where (A:X\to Y) is linear and (f) and (g) are proper convex functions. Conjugacy gives the associated Fenchel dual problem
[ \sup_{y^\in Y^} \bigl(-f^(-A^y^)-g^(y^*)\bigr). ]
The Fenchel–Young inequality implies weak duality: every dual objective value is bounded above by every primal objective value. Equality of the optimal values requires a qualification condition, commonly expressed through continuity at a feasible point or through a relative-interior relation between the domains.
For inequality-constrained problems, the same structure appears through the Lagrangian. Consider the minimization of (f(x)) subject to convex inequalities (g_i(x)\leq 0). Nonnegative multipliers produce affine lower bounds on the constrained optimum. Under Slater's condition, strict feasibility supplies the separation needed for strong duality and multiplier existence.
The resulting optimality relations are the Karush–Kuhn–Tucker conditions. In the convex setting, these conditions combine primal feasibility, dual feasibility, complementary slackness, and a subdifferential stationarity inclusion. When an appropriate qualification condition holds, they characterize global optimality rather than merely local stationarity.
Projections and proximal mappings
If (C) is a nonempty closed convex subset of a Hilbert space, every point (x) has a unique nearest point in (C). The resulting map (P_Cx) is the metric projection. It is characterized by
[ \langle x-P_Cx,y-P_Cx\rangle\leq 0 \qquad\text{for every }y\in C. ]
The projection is a special case of the proximal operator. For a proper lower-semicontinuous convex function (f) and a parameter (\lambda>0),
[ \operatorname{prox}_{\lambda f}(x)
\underset{y}{\operatorname{argmin}} \left( f(y)+\frac{1}{2\lambda}\lVert x-y\rVert^2 \right). ]
The quadratic term makes the objective strongly convex, so the minimizer is unique in a Hilbert space. The proximal point (p=\operatorname{prox}_{\lambda f}(x)) satisfies
[ \frac{x-p}{\lambda}\in\partial f(p). ]
Consequently,
[ \operatorname{prox}_{\lambda f}
(I+\lambda\partial f)^{-1}, ]
which identifies the proximal map with the resolvent of the subdifferential operator.
The corresponding Moreau envelope is
[ e_\lambda f(x)
\inf_y \left( f(y)+\frac{1}{2\lambda}\lVert x-y\rVert^2 \right). ]
It replaces a nonsmooth convex function by a finite and differentiable regularization under standard Hilbert-space assumptions. Its gradient is determined by the displacement between (x) and its proximal point.
Structural significance
Convex analysis treats geometric constraints, nonsmooth objectives, and dual variables as manifestations of a single separation structure. Indicator functions translate sets into extended-real-valued functions, while conjugates translate supporting hyperplanes into dual objectives. Subdifferentials then express both optimality and monotonicity through one set-valued operator.
The theory does not eliminate the need for regularity assumptions. Closedness governs representation by conjugates, topological duals govern separation, and domain qualifications govern exact subdifferential calculus. These conditions describe where the underlying convex sets possess enough interior structure for geometric separation to yield normalized and continuous supporting functionals.