1 Fenchel conjugates
1.1 Definition of the convex conjugate
For a function \(f:\mathbb{R}^n\to \overline{\mathbb{R}}\) (where \(\overline{\mathbb{R}}=\mathbb{R}\cup\{+\infty\}\)), the Fenchel (convex) conjugate \(f^*:\mathbb{R}^n\to \overline{\mathbb{R}}\) is defined by \[ f^*(y)=\sup_{x\in\mathbb{R}^n}\{\langle y,x\rangle - f(x)\}. \] This transforms the original function into another convex function, encoding how large linear functionals can be relative to \(f\).
1.2 Basic properties (convexity, lower semicontinuity, involution)
The conjugate \(f^*\) is always convex, even when \(f\) is not. More refined properties follow from regularity assumptions on \(f\): in general, \(f^*\) is also lower semicontinuous in the standard topology once closure operations are accounted for. A central theme is that conjugation is an involution only after taking a suitable closure; applying conjugation twice yields a “closed convex envelope” of the original function rather than recovering \(f\) pointwise.
1.3 Examples of conjugate pairs
Common conjugate pairs include:
| - Norms and support functions: for a norm \(\|\cdot\|\), the conjugate of \(\|x\|\) is related to the indicator of the dual unit ball, and vice versa. |
|---|
| - Quadratic functions: if \(f(x)=\tfrac12\|x\|^2\), then \(f^*(y)=\tfrac12\|y\|^2\) under the matching inner product. |
- Indicator functions of convex sets: if \(f=\delta_C\) is \(0\) on \(C\) and \(+\infty\) outside, then \(f^*=\sigma_C\), the support function of \(C\).
These examples illustrate how conjugation swaps constraints (indicators) with linear growth bounds (support functions).
1.4 Geometric interpretation via supporting hyperplanes
The quantity \(\langle y,x\rangle - f(x)\) can be read as the vertical gap between the affine function \(x\mapsto \langle y,x\rangle\) and the graph of \(f\). The supremum over \(x\) selects the tightest such affine upper model. When \(f\) is closed and convex, the points where \(f(x)+f^*(y)=\langle y,x\rangle\) correspond to supporting hyperplanes to the epigraph of \(f\). In this way, conjugates describe the geometry of how convex functions can be “tangent from above.”
2 The primal–dual setup
2.1 Primal problem in convex form
A typical convex optimization problem is written in terms of minimizing a proper convex function: \[ \inf_{x\in\mathbb{R}^n} \{ f(x) \} \quad \text{or} \quad \inf_{x} \{ f(x)+g(Ax) \}, \] where \(f\) and \(g\) are convex (possibly extended-real-valued) and \(A\) is a linear map. The Fenchel framework is especially convenient for problems expressed as a sum of convex functions composed with linear operators.
2.2 Constructing the dual function
The conjugate transforms minimization into maximization by using the identity \[ f(x)=\sup_{y}\{\langle y,x\rangle - f^*(y)\} \] when \(f\) is closed and convex (or after appropriate closure). Substituting such representations into the primal infimum and interchanging \(\inf\) and \(\sup\) in a controlled way yields a dual objective defined by conjugates. The resulting dual function is typically an upper bound on the primal optimal value.
2.3 The Fenchel dual problem
For the composite form \(\inf_x \{ f(x)+g(Ax)\}\), the Fenchel dual can be written as \[ \sup_{y}\{ -f^*(A^\top y) - g^*( -y)\}, \] under standard conventions about the adjoint operator \(A^\top\). The dual variables correspond to the conjugate of the “linearized” coupling term, and feasibility is expressed implicitly through the finiteness of conjugates.
2.4 Weak duality and inequality directions
Weak duality states that the dual optimal value never exceeds the primal optimal value (for the common sign conventions used above). This is derived directly from the definition of conjugate as a supremum: for any primal candidate \(x\) and dual candidate \(y\), \[ f(x)+g(Ax) \;\ge\; -f^*(A^\top y)-g^*(-y). \] Taking the infimum over \(x\) and the supremum over \(y\) produces the inequality direction between optimal values without requiring strong regularity conditions.
3 Fenchel duality theorem
3.1 Strong duality: equality of optimal values
Strong duality asserts that, under suitable assumptions, the infimum of the primal equals the supremum of the dual: \[ \inf_x (f(x)+g(Ax)) \;=\; \sup_y \big(-f^*(A^\top y)-g^*(-y)\big). \] This equality is not automatic; it depends on how the functions behave near feasible points and on whether their epigraphs can be separated without “gap.”
3.2 Constraint qualification conditions
Strong duality is guaranteed by constraint qualification conditions expressed in convex-analytic terms. Typical forms require that there exists at least one point where relevant functions are finite and that an interiority-like condition holds for the domains of \(f\) and \(g\) after linear transformation. These conditions prevent pathological situations where the duality gap becomes nonzero.
3.3 Roles of closedness and properness
Properness (not identically \(+\infty\) and never \(-\infty\)) ensures meaningful optimization. Closedness (lower semicontinuity) ensures that conjugation captures the correct “closed convex hull” of the function. If a function is not closed, its biconjugate corrects it: the duality theorem effectively involves closed convex envelopes, so missing closedness can lead to apparent failures unless corrected by taking closures.
3.4 Relation to separating hyperplane theorems
A deeper mechanism behind strong duality is geometric separation. The primal–dual gap can be viewed as an obstruction to separating certain convex sets in an affine space. When appropriate regularity holds, the separating hyperplane theorem yields the existence of dual certificates and converts inequality (weak duality) into equality (strong duality). Thus, Fenchel duality can be interpreted as an analytic reformulation of separation results in convex geometry.
4 Optimality conditions
4.1 Subdifferential characterization (KKT-type conditions)
Fenchel duality supplies optimality conditions via subgradients. For closed convex functions, the condition \[ y\in \partial f(x) \] means that \(f(z)\ge f(x)+\langle y,z-x\rangle\) for all \(z\). In primal–dual problems, optimality typically occurs when primal and dual variables satisfy inclusions involving subdifferentials of \(f\) and \(g\) at corresponding points.
4.2 Attainment and existence of dual optimizers
The theorem may guarantee that optimal values coincide, but existence of maximizers still depends on compactness or other regularity properties. In practice, if the dual objective is upper semicontinuous on a nonempty compact feasible region (or if coercivity provides boundedness), then a dual optimizer exists. Dual attainment is closely tied to whether minimizing sequences in the primal have accumulation points and whether conjugate objectives behave well at infinity.
4.3 Complementary slackness in conjugate form
Complementary slackness appears in Fenchel form as equality cases of Fenchel’s inequality: \[ f(x)+f^*(y)\ge \langle y,x\rangle, \] with equality if and only if \(y\in \partial f(x)\). Similar equalities hold for each conjugate component in a composite problem. These conditions play the same role as classical complementary slackness, but they are expressed through subgradient membership rather than through products of primal and constraint slack variables.
4.4 Primal–dual pairing via subgradients
When strong duality holds, optimal primal–dual pairs \((x^*,y^*)\) can be characterized by the coupled subgradient relations \[ A^\top y^*\in \partial f(x^*), \qquad -y^*\in \partial g(Ax^*), \] for the common composite formulation. Such relations provide a practical way to verify optimality: once one candidate pair is proposed, checking the subgradient inclusions certifies that both sides of the duality coincide.
5 Special cases and connections
5.1 Fenchel–Moreau theorem (biconjugation)
The Fenchel–Moreau theorem states that for a proper lower semicontinuous convex function \(f\), \[ f^{}=f, \] where \(f^{}\) denotes the conjugate of the conjugate. If \(f\) lacks lower semicontinuity or convexity, then \(f^{**}\) yields the largest lower semicontinuous convex function lying below \(f\). This theorem explains why conjugation can be used to “close and convexify” optimization models and why strong duality often involves closed convex envelopes.
5.2 Links to Lagrangian duality
Lagrangian duality introduces multipliers for constraints and forms a dual function by minimizing a Lagrangian over primal variables. Fenchel duality can recover Lagrangian duality by encoding constraints through indicator functions and incorporating linear operators through conjugates. Under suitable reformulations, the resulting dual problem matches the classical dual expressed in multiplier form, while Fenchel theory offers a function-based view that works smoothly for inequality-free convex formulations too.
5.3 Fenchel duality for infimal convolution
Infimal convolution combines functions via \[ (f \infconv g)(x)=\inf_{u}\{ f(u)+g(x-u)\}. \] Conjugation converts infimal convolution into addition of conjugates: \[ (f \infconv g)^* = f^* + g^*, \] when interpreted appropriately for extended-real-valued functions. This connection is useful for deriving duals of problems involving sums under variable splitting and for analyzing regularization terms that arise through such convolutions.
5.4 Connections to monotone operator theory
Subdifferentials of proper closed convex functions are maximally monotone operators. Fenchel duality can therefore be expressed in operator terms, where dual variables correspond to resolvents or inverses related to these monotone operators. This bridges convex optimization with variational inequalities and operator splitting methods, providing structural explanations for convergence and stability in algorithms.
6 Computational and analytic applications
6.1 Deriving dual problems for regularized optimization
Many modern optimization tasks include regularizers such as norms, sparsity-inducing penalties, or strongly convex terms. Fenchel conjugates offer an efficient route to dual formulations, sometimes producing simpler constraints or separable structure. In practice, the dual problem may involve projection-like operations onto sets defined by conjugates, making it attractive for numerical solvers.
6.2 Duality in variational problems
Variational problems often seek minimizers of energy functionals subject to constraints. When those energies include convex terms and linear couplings, Fenchel duality rewrites the search for primal minimizers as a maximization over dual potentials. This can simplify analysis, for example by turning difficult primal conditions into dual feasibility checks and by enabling estimates directly from dual objectives.
6.3 Stability under perturbations
Convex duality has a perturbation theory: small changes in the problem data affect both primal and dual optimal values in a controlled manner. Conjugate-based formulations make it possible to quantify sensitivity using subgradients of value functions and to characterize how optimal solutions shift. This is particularly relevant for regularization path analysis and for proving robustness of optimization models.
6.4 Using dual formulations for bounds and algorithms
Even when strong duality is unavailable, the dual problem supplies computable lower or upper bounds (depending on sign conventions) on the primal optimum. These bounds are valuable for branch-and-bound schemes, screening rules, and stopping criteria. For algorithms, dual structure can motivate coordinate updates, primal–dual methods, and operator splitting approaches that exploit smoothness or separability present in conjugate forms.
7 Illustrative examples
7.1 Duality for norms and support functions
| Let \(f(x)=\|x\|\) for a norm \(\|\cdot\|\). The conjugate \(f^*\) becomes an indicator of the dual unit ball: |
|---|
\[
| f^*(y)=\delta_{\{y:\|y\|_* \le 1\}}(y), |
|---|
\]
| where \(\|\cdot\|_*\) is the dual norm. Conversely, the conjugate of an indicator set is the support function of that set. These relationships make it straightforward to derive dual constraints for problems involving norm regularization, such as converting \(\ell_1\)-regularized objectives into dual feasible regions described by \(\ell_\infty\) constraints. |
|---|
7.2 Quadratic objectives and conjugate computation
| For \(f(x)=\tfrac{1}{2}\|x\|^2\), the conjugate is \(f^*(y)=\tfrac{1}{2}\|y\|^2\) (with the norm induced by the inner product). In constrained composite problems, this leads to dual objectives that are also quadratic, often producing smooth dual functions. The resulting dual optimality conditions can yield explicit relationships between primal solutions and dual multipliers, including scaling identities. |
|---|
7.3 Entropy-like functions and log-sum-exp duals
Entropy-related convex functions frequently appear in probability and information theory contexts. A common example is the negative entropy or the log-partition function, whose conjugate is tied to log-sum-exp expressions. In optimization, these conjugates enable dual formulations where constraints take the form of probability-simplex conditions and dual objectives become tractable smooth functions, supporting efficient gradient-based methods.
7.4 Indicator functions and dual feasible sets
If \(f=\delta_C\) for a closed convex set \(C\), then \(f^*=\sigma_C\), the support function: \[ \sigma_C(y)=\sup_{x\in C}\langle y,x\rangle. \] In dual problems, indicator functions in the primal become support functions in the dual, meaning that dual objectives involve evaluating linear maxima over sets. This interpretation often turns feasibility questions into geometric ones, such as checking whether a proposed dual vector lies within a certain polar set.
8 Common pitfalls and assumptions
8.1 Properness vs. extended-real-valued functions
Because conjugation is defined over extended-real values, some functions may take \(+\infty\) outside their effective domains. Confusing “undefined” with “infinite cost” can lead to incorrect dual derivations. Ensuring properness and correctly tracking where functions are finite is essential for identifying valid feasible sets for both primal and dual problems.
8.2 Lower semicontinuity issues
If a function is convex but not lower semicontinuous, then conjugation and biconjugation modify it. In such cases, a duality theorem may still apply, but it will concern the closed convex envelope rather than the original function. Neglecting this can produce apparent contradictions between primal and dual computations.
8.3 When strong duality may fail
Strong duality can fail when constraint qualification conditions do not hold, even for convex problems. Typical causes include lack of interior points in relevant domains, discontinuities of the value function, or “gaps” created by closure requirements. Weak duality remains valid, so the discrepancy manifests as a nonzero duality gap.
8.4 Interpreting empty subdifferentials
Subdifferentials can be empty if the point lies outside the relative interior of the effective domain or if regularity assumptions fail. In optimality conditions, an empty subdifferential means no supporting hyperplane exists with the desired slope. Care is needed when using subgradient inclusions as certificates: one must verify that the involved subdifferentials are nonempty at the candidate points.