1 Definition and Preliminaries
1.1 Convex functions and extended-real values
In convex analysis, a function \(f\) defined on a real vector space \(X\) is called convex if its epigraph is a convex set. Often \(f\) is allowed to take values in the extended real line \(\overline{\mathbb{R}}=\mathbb{R}\cup\{+\infty\}\), or sometimes \(\mathbb{R}\cup\{-\infty\}\), to conveniently encode constraints and infeasible points. Allowing \(+\infty\) is particularly common because it turns hard constraints into part of the objective: infeasible points are assigned infinite cost, making optimization problems uniform in form.
A function is called proper if it never attains \(-\infty\) and is not identically \(+\infty\). The effective domain \(\operatorname{dom} f\) consists of points where \(f(x)<+\infty\). These conventions are essential for the biconjugate theorem, which concerns functions possibly taking \(+\infty\) values.
1.2 Convex conjugate (Legendre–Fenchel transform)
Given a function \(f:X\to\overline{\mathbb{R}}\), its convex conjugate (also called the Legendre–Fenchel transform) is defined on the dual space \(X^\*\) by \[ f^\*(y)=\sup_{x\in X}\{\langle y,x\rangle - f(x)\}, \] where \(\langle y,x\rangle\) denotes the dual pairing. The conjugate is always convex (as a function of \(y\)), regardless of whether \(f\) is convex. It may also take the value \(+\infty\), depending on growth and domain properties.
Intuitively, \(f^\*\) re-expresses \(f\) in terms of linear “test” functions \(\langle y,x\rangle\). The supremum chooses the supporting linear behavior that best offsets the penalty \(f(x)\).
1.3 Lower semicontinuity and closure operations
Lower semicontinuity (lsc) is a topological regularity condition. A function \(g\) is lsc if for every real \(\alpha\), the sublevel set \(\{x: g(x)\le \alpha\}\) is closed, or equivalently if \(g(x)\le \liminf_{x'\to x} g(x')\).
In the context of biconjugation, lsc closure is required because taking conjugates tends to produce functions with better regularity properties than an arbitrary original \(f\). If \(f\) is not lsc or not convex, the double conjugate \(f^{\*\*}\) will generally produce a “best” convex lsc majorant or a related envelope, rather than returning \(f\) exactly.
1.4 Notation, domains, and basic examples
Some standard notation used throughout:
- \(\operatorname{dom} f=\{x: f(x)<+\infty\}\)
- epigraph \(\operatorname{epi} f=\{(x,t): f(x)\le t\}\)
- conjugate \(f^\*(y)\) and biconjugate \(f^{\*\*}(x)\)
Basic examples illustrate the mechanism:
- If \(f\) is an indicator of a convex set (finite on the set and \(+\infty\) outside), its conjugate is a support function.
| - If \(f(x)=\frac12\|x\|^2\) (in a Hilbert space setting), its conjugate is again quadratic, reflecting the duality between quadratic forms and their Legendre transforms. |
|---|
- For piecewise-linear convex functions, conjugation yields piecewise-linear conjugates whose slopes correspond to subdifferential values.
2 Statement of the Biconjugate Theorem
2.1 General formulation via double conjugation
Let \(f:X\to\overline{\mathbb{R}}\). Define the biconjugate by \[ f^{\*\*}(x)=\sup_{y\in X^\*}\{\langle y,x\rangle - f^\*(y)\}. \] The biconjugate theorem states that \(f^{\*\*}\) recovers \(f\) after applying the appropriate convexity and lsc closure operations.
A fundamental inequality always holds (Fenchel’s inequality): for every \(x\in X\), \[ f^{\*\*}(x)\le f(x), \] or in a more common equivalent form, \[ f(x)\ge f^{\*\*}(x). \] When \(f\) is convex and lsc (under appropriate topological assumptions on \(X\)), equality holds: \(f^{\*\*}=f\).
2.2 Role of lower-semicontinuity and convexity
The theorem’s structure is best understood as a “regularization principle.” If \(f\) lacks convexity, then \(f^\*\) encodes the convex hull behavior compatible with linear supports of \(\langle y,x\rangle-f(x)\). If \(f\) lacks lower semicontinuity, conjugation effectively replaces \(f\) by its lower semicontinuous envelope in the convex category.
Consequently, for general proper functions, \(f^{\*\*}\) is the convex lsc envelope associated with \(f\): it is convex, lsc, and lies below \(f\); moreover, it is maximal among convex lsc functions dominated by \(f\) (or equivalently, it is the tightest convex lsc minorant consistent with the conjugate representation).
2.3 Equality conditions and the convex-lsc envelope
A common precise statement is: \[ f^{\*\*}=\operatorname{cl}\,\operatorname{conv}(f), \] where \(\operatorname{conv}(f)\) denotes the largest convex function majorized by \(f\) (or more carefully, the convex hull construction in the epigraph sense), and \(\operatorname{cl}\) denotes lower semicontinuous closure in the relevant topology.
In practice, equality \(f^{\*\*}=f\) holds whenever \(f\) is:
1 Definition and Preliminaries
2 Statement of the Biconjugate Theorem
and proper in the relevant setting. When these conditions fail, \(f^{\*\*}\) is still meaningful—it gives the best approximation of \(f\) by a convex lsc function compatible with conjugate data.
2.4 Relation to the Fenchel–Moreau theorem
The Fenchel–Moreau theorem is often presented as the definitive biconjugate statement in general locally convex spaces. It asserts that for a proper convex lsc function \(f\), one has \(f=f^{\*\*}\). For arbitrary proper functions, the biconjugate yields the convex lsc hull, sometimes called the “Fenchel–Moreau closure” of \(f\).
Thus, the biconjugate theorem and Fenchel–Moreau theorem are closely linked: the biconjugate theorem is the core algebraic operation (double conjugation), while Fenchel–Moreau characterizes when the operation returns the original function and when it yields the lsc convex envelope.
3 Consequences and Interpretations
3.1 Convexification and lower-semicontinuous closure
Double conjugation can be viewed as a systematic correction of two defects:
- Nonconvexity is “fixed” by replacing \(f\) with the maximal convex function not exceeding it (in the envelope sense).
- Lack of lsc is “fixed” by taking the lower semicontinuous closure of that convexified object.
This interpretation makes biconjugation a canonical regularization tool. Instead of manually convexifying and then smoothing discontinuities, the conjugate machinery performs both steps automatically in one algebraic procedure.
3.2 Geometric meaning (supporting hyperplanes viewpoint)
Geometrically, conjugation reflects supporting hyperplanes to the epigraph. For convex lsc functions, every boundary point of the epigraph can be supported by some continuous affine functional. The conjugate collects these supports through a supremum over linear functionals.
Therefore, the biconjugate theorem can be read as: the epigraph of \(f\) is exactly determined by all its supporting hyperplanes when \(f\) is convex and lsc. If the function is not convex or not lsc, some “virtual” supporting structures still define an epigraph, but it corresponds to the convex lsc envelope rather than the raw original graph.
3.3 Epigraph and dual representation
The epigraph perspective leads to a dual representation:
- \(f^\*\) describes how \(f\) behaves when tested against linear functionals.
- \(f^{\*\*}\) reconstructs the smallest closed convex set (in epigraph form) compatible with those tests.
In optimization theory, this becomes a bridge from primal descriptions (functions of \(x\)) to dual descriptions (functions of \(y\)), where \(y\) often represents multipliers or dual variables arising from linear constraints and convex penalties.
3.4 Recovery of a function from its conjugate data
Since \(f^{\*\*}\) is computable from \(f^\*\), the theorem provides a method to recover the “regularized” version of \(f\). Even when \(f\) is complicated, it may be easier to compute or approximate the conjugate, and then reconstruct \(f^{\*\*}\).
This recovery is especially valuable in variational analysis, where the objects of interest are often convex and lsc by construction, making equality conditions more likely. For nonconvex or nonsmooth problems, biconjugation still supplies an informative convex surrogate.
4 Applications in Convex Optimization
4.1 Dual problems and Fenchel duality
In Fenchel duality, one writes the primal objective as a convex function plus (possibly) linear coupling, then uses conjugates to form a dual objective. A typical setup is minimizing \[ \inf_x \{ f(x)+g(Ax)\}, \] where \(A\) is linear. Conjugation yields \[ g(Ax)=\sup_y \{\langle y,Ax\rangle - g^\*(y)\}, \] and interchange of supremum and infimum under suitable assumptions leads to a dual problem expressed in terms of \(f^\*\) and \(g^\*\).
The biconjugate theorem ensures that when the involved functions are convex and lsc, the primal objective is faithfully represented through the conjugate construction, enabling rigorous dual formulations.
4.2 Strong duality under standard regularity assumptions
Strong duality refers to equality of optimal values between primal and dual problems. While weak duality holds broadly, strong duality typically requires regularity conditions such as:
- existence of a point where certain constraint qualifications are satisfied,
- closedness of relevant epigraphs,
- boundedness or continuity assumptions that justify interchange of optimization operations.
In many convex settings, biconjugation underpins these results by ensuring that the convex lsc closures used implicitly by conjugate algebra align with the original model, so that no “gap” is introduced by taking conjugates.
4.3 Subgradient and stationarity characterizations
Optimality conditions in convex optimization can often be expressed via subgradients. For conjugate pairs, there is a fundamental relationship: \[ y\in \partial f(x) \quad \Longleftrightarrow \quad x\in \partial f^\*(y), \] under standard assumptions. This correspondence provides stationarity rules in primal–dual form: a point \(x\) is optimal if there exists a dual variable \(y\) satisfying inclusion relations among subdifferentials induced by conjugation.
Such conditions resemble KKT systems: rather than explicitly introducing Lagrange multipliers for every constraint, conjugate dual variables naturally emerge from the transform.
4.4 Constructing solutions from primal–dual relationships
Once the subgradient correspondence is available, one can often reconstruct primal or dual solutions from each other. If an optimizer \(y^\*\) for the dual is known, then any \(x\) satisfying \[ y^\*\in \partial f(x) \] and the matching coupling constraints can be recovered as a primal optimizer (again subject to regularity). This is particularly useful in algorithm design, where dual iterates are computed and primal solutions are recovered by solving subgradient inclusion problems or via projection steps tailored to the structure of \(f\) and \(g\).
5 Subgradients and Duality Maps
5.1 Conjugate subdifferential relationships
Let \(f\) be proper, convex, and lsc. The subdifferential \(\partial f(x)\subseteq X^\*\) consists of all \(y\) such that \[ f(z)\ge f(x)+\langle y,z-x\rangle \quad \text{for all } z. \] For conjugate functions, the biconjugate theorem supports the equivalence between primal and dual subgradients:
- \(y\in\partial f(x)\) implies \(f(x)+f^\*(y)=\langle y,x\rangle\),
- and the equality case characterizes the subgradient membership.
This connection is a central computational tool: it turns abstract duality into concrete inclusion tests.
5.2 KKT-like conditions via conjugation
Consider a convex optimization problem with a form that admits conjugate modeling. Optimality can be expressed through subgradient conditions that correspond to generalized KKT relations. For instance, in problems involving \(f(x)\) and \(g(Ax)\), optimality may require: \[ 0\in \partial f(x^\*) + A^\*\partial g(Ax^\*), \] together with feasibility constraints. Conjugate mappings rewrite \(\partial g\) in terms of \(\partial g^\*\), making it possible to characterize solutions using dual variables and to derive complementary relations of the form \[ g(Ax^\*) + g^\*(y^\*) = \langle y^\*,Ax^\*\rangle. \]
5.3 Differentiability special cases
If \(f\) is differentiable at \(x\), then \(\partial f(x)=\{\nabla f(x)\}\). Under suitable smoothness and strict convexity, this can make conjugate dual variables unique and turns inclusion relations into equations. For example, if \(f\) is Legendre-type (essentially smooth and strictly convex), the mapping \(x\mapsto \nabla f(x)\) becomes bijective between appropriate interiors of domains, and the conjugate gradient satisfies \[ \nabla f^\*(\nabla f(x))=x. \] These identities are the differentiable analogs of the subdifferential correspondences underlying biconjugation.
5.4 Example: quadratic and indicator functions
Two canonical examples clarify the mechanism:
| - Quadratic: In Euclidean spaces, \(f(x)=\frac12\|x\|^2\) has conjugate \(f^\*(y)=\frac12\|y\|^2\). The gradient relation is \(\nabla f(x)=x\), and the conjugate subgradient condition becomes \(y=x\). |
|---|
- Indicator: If \(f=\delta_C\) where \(\delta_C(x)=0\) for \(x\in C\) and \(+\infty\) otherwise (and \(C\) is convex and closed), then
\[ f^\*(y)=\sup_{x\in C}\langle y,x\rangle \] is the support function of \(C\). The subgradient condition connects optimal dual vectors with supporting hyperplanes to \(C\) at primal points.
6 Examples and Worked Computations
6.1 Simple one-dimensional conjugates
In one dimension, conjugates can be computed by maximizing \(\{yx-f(x)\}\) over \(x\). If \(f\) is convex and smooth, the maximizer satisfies \(y=f'(x)\), leading to an explicit formula. For piecewise definitions, the supremum often occurs at endpoints of intervals or at points where slopes match \(y\).
These computations illustrate how conjugation converts curvature information in \(f\) into growth behavior in \(f^\*\), with the dual variable \(y\) acting as a “slope parameter.”
6.2 Indicator functions of convex sets
For a closed convex set \(C\subseteq X\), define \(\delta_C(x)=0\) on \(C\) and \(+\infty\) outside. Then the conjugate is \[ \delta_C^\*(y)=\sup_{x\in C}\langle y,x\rangle, \] the support function. Double conjugation returns \(\delta_C\) when \(C\) is closed and convex, reflecting that the epigraph structure is already determined by its supporting hyperplanes.
This example highlights how feasibility constraints become dual objects that measure directional extent of the feasible set.
6.3 Norms and support functions
| For norms, conjugates relate to dual norms. If \(f(x)=\|x\|\), conjugation gives a function that is finite on a unit ball in the dual norm and infinite outside, up to constants. More generally, for gauge functions and their polars, conjugation produces support functions of corresponding sets. |
|---|
Such results are widely used in regularization: norms in the primal correspond to constrained sets in the dual, enabling dual certification and bounding techniques.
6.4 Piecewise-linear convex functions
Piecewise-linear convex functions have conjugates that are also piecewise-linear (possibly after domain restrictions). Breakpoints in \(f\) correspond to ranges of subgradients, and the conjugate reflects these slope intervals as domain constraints in \(f^\*\).
Working through a piecewise example typically involves:
1 Definition and Preliminaries
2 Statement of the Biconjugate Theorem
3 Consequences and Interpretations
These computations concretely demonstrate how biconjugation reconstructs the convex lsc hull of the original piecewise description.
7 Variants and Related Results
7.1 Proper vs improper functions and feasibility issues
Biconjugation is typically stated for proper functions; otherwise, conjugates can become degenerate. If \(f\equiv +\infty\), then \(f^\*\equiv -\infty\) in extended conventions, and double conjugation is not informative. If \(f\) takes \(-\infty\), conjugation can similarly break down.
In optimization modeling, ensuring properness corresponds to ensuring feasibility and meaningful objective values on at least one point.
7.2 Biconjugation on different topological vector spaces
The Fenchel–Moreau theorem depends on the underlying topological structure, often requiring a locally convex topological vector space with an appropriate notion of continuous dual. In such settings, the conjugate is defined using the dual pairing with continuous linear functionals, and lsc closure is taken with respect to the given topology.
On Banach spaces, one uses the continuous dual; on more general locally convex spaces, the dual may be larger or different, changing the resulting conjugate. The general pattern remains: under the appropriate topology, double conjugation yields the convex lsc envelope.
7.3 Connections to envelope theorems
Envelope theorems describe how optimal value functions depend on parameters; conjugates can be interpreted as envelope operators through supremal constructions. Since \(f^\*\) is defined by a supremum over affine functions, it behaves like a convex envelope of a family of linear models. The biconjugate then serves as a closure of that envelope back in the primal variable.
This viewpoint connects variational duality with convex envelopes and supports geometric interpretations in terms of outer approximations.
7.4 Links to separating hyperplane theorems
Separating hyperplane results are closely tied to conjugation. When a point lies outside a closed convex set, one can separate it by a continuous affine functional; these affine functionals correspond to subgradients and dual variables. The biconjugate theorem can be proved using separation: supporting hyperplanes generate the conjugate representation, and the double conjugate reconstructs the closed convex structure.
Thus, the biconjugate theorem functions as an analytic form of geometric separation.
8 Limitations and Edge Cases
8.1 When double conjugation fails to recover the original function
If \(f\) is not convex or not lower semicontinuous, the identity \(f=f^{\*\*}\) generally fails. The biconjugate will instead provide a convex lsc minorant of \(f\), often strictly smaller at points where the original function is “too nonconvex” or has downward jumps.
A practical takeaway is that double conjugation should be viewed as reconstruction of the best convex lsc approximation compatible with the conjugate transform, not as a guaranteed exact inversion for arbitrary functions.
8.2 Non-convex functions and the “convexification” outcome
For nonconvex \(f\), the conjugate construction effectively disregards portions of the graph that cannot be supported by linear functionals. The resulting \(f^{\*\*}\) corresponds to a convexified representation (in the epigraph sense). In some cases, it matches the convex hull of \(f\) over relevant ranges; in others, it produces a more subtle envelope reflecting the closure and domain constraints.
This “convexification” explains why conjugate methods are naturally suited to convex problems but still useful as relaxations for nonconvex settings.
8.3 Non-lower-semicontinuous behavior
If \(f\) has discontinuities from below (or lacks closed epigraph), conjugation introduces lower semicontinuous closure. Points where \(f\) drops abruptly may be filled in by limit infima coming from nearby convex supports. Consequently, \(f^{\*\*}\) is lsc even if \(f\) is not.
In applications, this means that dual-based models correspond to the lsc closed version of the primal objective, which can matter when computing optimal values or certificates.
8.4 Domain mismatches and extended-value pitfalls
Since conjugates involve extended-real values, errors can occur when improper domain assumptions are made. For example, if \(f\) is not proper, conjugation may become ill-behaved. If \(f\) assigns \(+\infty\) on large regions, then the supremum defining \(f^\*\) may collapse to values reflecting only feasible points.
Domain mismatches can also happen when \(f\) is defined on one space but conjugation is taken relative to a different pairing or topology. Correct identification of the dual space and the continuity structure is therefore essential.
9 Computational Aspects
9.1 Practical computation of conjugates
Computing \(f^\*\) typically requires solving \[ f^\*(y)=\sup_x \{\langle y,x\rangle - f(x)\}. \] For common convex functions—quadratics, norms, indicators, and log-sum-exp—closed-form conjugates exist. For more complex models, computation may be done numerically by optimizing a convex function in \(x\) for each \(y\), or by exploiting structural decompositions (e.g., separability across coordinates).
In practice, one often computes \(f^\*\) implicitly through known subgradient relations rather than performing the supremum directly.
9.2 Numerical implications for dual formulations
Dual formulations derived via conjugates can be computationally advantageous or challenging. They may reduce dimension (depending on \(A\) and the structure of \(f^\*\) and \(g^\*\)), or they may convert constraints into penalties with simpler proximal operators. However, if \(f^\*\) lacks a tractable form, evaluating the dual objective becomes expensive.
The biconjugate theorem provides conceptual reassurance: when the problem is convex and regular enough, dual computations remain consistent with the primal objective up to the convex lsc envelope, so approximate dual solutions can often be interpreted reliably.
9.3 Approximation schemes using conjugate closures
When \(f\) is not exactly convex or lsc, one can use \(f^{\*\*}\) as a convex regularized surrogate. Approximation schemes may proceed by:
1 Definition and Preliminaries
2 Statement of the Biconjugate Theorem
3 Consequences and Interpretations
This approach is common in variational problems where direct convexification is difficult, but conjugate computations are manageable.
9.4 Error bounds in approximate biconjugation
When conjugates are computed approximately (e.g., via numerical optimization or discretization), the biconjugate reconstruction inherits error. Error bounds often relate to how far the approximate conjugate is from \(f^\*\) and how that translates into bounds for \(f^{\*\*}\).
While general sharp bounds depend on norms, topologies, and regularity assumptions, a common theme is stability: if \(f^\*\) is approximated well on the relevant set of dual variables, then \(f^{\*\*}\) is approximated well on the primal region where the supremum in the biconjugate is effectively attained.
10 Further Reading and References
10.1 Core textbooks in convex analysis
Standard references include textbooks that develop Fenchel duality, subgradients, and conjugate functions in depth, typically in chapters on convex analysis fundamentals and duality.
Look for treatments that explicitly connect conjugation to the epigraph geometry and include proofs of the Fenchel–Moreau theorem.
10.2 Standard lecture notes and surveys
University course notes often provide streamlined proofs and worked examples, with emphasis on computational use in optimization. Surveys may also focus on special cases such as conjugates of norms, indicator functions, and Legendre-type functions.
When consulting notes, it is useful to check whether they assume Banach space structure, local convexity, or additional regularity.
10.3 Historical context of convex conjugation
The Legendre–Fenchel transform generalizes earlier ideas from classical mechanics (Legendre transforms) and extends them to nonsmooth convex settings (Fenchel). The biconjugate theorem and Fenchel–Moreau theorem formalize the idea that convex functions can be reconstructed from their “linear support” data.
Historical notes often trace the development from variational calculus to functional analysis and modern optimization.
10.4 Suggested exercises and canonical problem sets
Canonical exercises include:
- deriving conjugates of common functions (quadratics, absolute value, indicators),
- proving Fenchel inequalities and equality characterizations,
- verifying conditions under which \(f=f^{\*\*}\),
- computing biconjugates from explicit conjugates,
- applying conjugation to derive dual problems for standard convex programs.
These exercises reinforce both computation and the conceptual envelope interpretation central to the biconjugate theorem.