The Fenchel Conjugate: Legendre Duality for Convex Functions

The precise definition and what it claims

Let X be a real locally convex topological vector space (e.g. ℝⁿ) with continuous dual X*, and let f: X → ℝ ∪ {+∞} be an extended-real-valued function. The Fenchel conjugate (or convex conjugate) f*: X* → ℝ ∪ {±∞} is

• f*(y) = sup_x∈X ( ⟨y, x⟩ − f(x) ).

Here ⟨y, x⟩ is the duality pairing (the dot product y·x in ℝⁿ). We call f proper if f(x) < +∞ for at least one x and f(x) > −∞ for all x. The core structural claim is twofold. First, f* is always convex and lower semicontinuous, regardless of whether f is — because it is a pointwise supremum of the affine functions y ↦ ⟨y, x⟩ − f(x), and any sup of affine (hence convex, lsc) functions is convex and lsc. Second, the Fenchel–Young inequality holds for all x, y:

• f(x) + f*(y) ≥ ⟨y, x⟩,

with equality exactly when y is a subgradient of f at x. This inequality is immediate from the definition of the supremum, yet it is the seed of essentially every duality bound in the theory.

The geometric picture: slopes instead of points

Fix a slope y. The affine function x ↦ ⟨y, x⟩ − c has graph a hyperplane of slope y sitting at height −c. Asking for the largest c such that this hyperplane stays below the graph of f everywhere is exactly asking for f*(y): the conjugate records, for each slope y, how far down you must drop the supporting hyperplane of that slope to touch the epigraph of f from below. So −f*(y) is the intercept of the tightest supporting line of slope y.

This is the deep idea: a convex function is completely determined by its family of supporting hyperplanes (a closed convex set equals the intersection of the closed half-spaces containing it). The conjugate is a bookkeeping device that catalogs those hyperplanes by their slopes. Passing from f to f* swaps the roles of point-coordinate and slope-coordinate — the epigraph of f, described by points (x, f(x)), gets re-described by the tangent-line data (y, −f*(y)). Because the description is lossless for convex closed epigraphs, doing it twice must return the original function.

The mechanism of the proof: separate the epigraph

The headline theorem is Fenchel–Moreau: if f is proper, convex, and lower semicontinuous, then f** = f, where f**(x) = sup_y(⟨y, x⟩ − f*(y)) is the conjugate of f*. The proof machinery is the separating hyperplane theorem (Hahn–Banach in geometric form).

• One direction is free: f**(x) ≤ f(x) always, because f** is the sup of affine minorants of f and every such minorant lies below f (this is just Fenchel–Young rearranged).
• For the reverse, suppose f**(x₀) < f(x₀). Then the point (x₀, f**(x₀)) lies strictly below the epigraph of f. The epigraph is a closed convex set (convexity of f gives convex; lower semicontinuity gives closed), so a closed convex set and an exterior point can be strictly separated by a hyperplane.
• That separating hyperplane, once its non-vertical part is extracted, is an affine minorant of f that at x₀ exceeds f**(x₀) — contradicting that f** is the supremum of all affine minorants.

The technical subtlety is handling vertical separating hyperplanes, which occur near the boundary of the domain; a short perturbation argument tilts them into genuine affine functions. Lower semicontinuity is precisely what makes the epigraph closed and hence separable.

Worked examples and the canonical special cases

A few conjugate pairs make the machinery concrete (all in ℝⁿ or ℝ):

• Quadratic: f(x) = ½‖x‖². The sup of ⟨y,x⟩ − ½‖x‖² is attained at x = y, giving f*(y) = ½‖y‖². The quadratic is its own conjugate — the unique self-dual function, and the fixed point of the transform.
• Power functions: f(x) = |x|ᵖ⁄p for p > 1 has f*(y) = |y|ᵍ⁄q with 1/p + 1/q = 1. Fenchel–Young here is exactly Young's inequality ab ≤ aᵖ/p + bᵍ/q, the backbone of Hölder's inequality.
• Exponential: f(x) = eˣ conjugates to f*(y) = y ln y − y for y > 0 (with f*(0)=0), the negative-entropy function driving large-deviations theory.
• Indicator of a set: for a convex set C, the indicator δ_C (which is 0 on C, +∞ off it) has conjugate δ_C*(y) = sup_x∈C⟨y, x⟩ = σ_C(y), the support function. This single identity is why support functions and gauges are conjugate objects.
• Norm: f(x) = ‖x‖ conjugates to the indicator of the dual-norm unit ball.

Why the hypotheses matter — and what breaks

Fenchel–Moreau demands proper, convex, and lower semicontinuous. Drop any one and f** = f can fail:

• Non-convex f. Take f(x) = min(1, x²) or any double-well. The biconjugate f** is the closed convex hull of f — the largest convex lsc minorant. So f** = conv(f) < f wherever f bulges above its convex hull. This is a feature: conjugating twice is how you convexify. It also explains why non-convex minimization has a duality gap: the dual problem secretly solves the convexified problem.
• Not lower semicontinuous. If f agrees with a convex lsc function except that it takes a larger value at one boundary point, f** fills that hole back in with the lsc value; you recover the lsc closure cl f, not f itself.
• Not proper. If f ≡ +∞, then f* ≡ −∞ and f** ≡ +∞ — consistent but degenerate; the honest non-degenerate theory needs a point of finiteness.

These connect the conjugate to the bipolar theorem (a set equals its double polar iff it is closed convex containing 0) and to Lagrangian duality, where the duality gap is exactly f(0) − f**(0) for the perturbation function f.

Applications: what the conjugate unlocks

The Fenchel conjugate is not a curiosity — it is the organizing principle of convex duality.

• Fenchel duality. For inf_x [f(x) + g(Ax)] the dual is sup_y [−f*(A*y) − g*(−y)]; under a constraint-qualification (relative-interior overlap of domains) strong duality holds. Linear-programming duality is the special case where f, g are indicators of polyhedra.
• Lagrangian / KKT. The dual function in nonlinear programming is a conjugate in disguise; weak duality is Fenchel–Young, and strong duality is Fenchel–Moreau plus Slater's condition.
• Optimization algorithms. The proximal operator and its Moreau envelope obey Moreau's decomposition x = prox_f(x) + prox_f*(x); this powers ADMM, mirror descent, and dual ascent.
• Mechanics and thermodynamics. The Legendre transform converts the Lagrangian L(q, q̇) into the Hamiltonian H(q, p), and internal energy into free energies — all special cases with smooth, strictly convex f.
• Probability. The cumulant generating function is a conjugate; its transform is the large-deviations rate function (Cramér's theorem).

The classical Legendre transform versus the Fenchel conjugate: the conjugate extends Legendre's smooth, invertible construction to all convex functions, including non-smooth and extended-real-valued ones.

Aspect	Legendre transform	Fenchel conjugate
Domain of definition	f smooth, strictly convex on an open interval/set	Any f: X → ℝ ∪ {+∞} (extended-real-valued)
Formula	f*(y) = ⟨y, x(y)⟩ − f(x(y)), where f′(x(y)) = y	f*(y) = sup_x (⟨y, x⟩ − f(x))
Requires differentiability?	Yes — needs f′ invertible	No — sup handles kinks and corners
Handles constraints / indicator functions?	No	Yes — δ_C conjugates to the support function σ_C
Involution property	f** = f where the inverse slope map exists	f** = f iff f convex, lsc, proper (Fenchel–Moreau)
Output for non-convex f	Undefined / ambiguous	Always convex; f** = conv(f), the closed convex hull