The function seen from its tangents

The previous rung establishes that a convex function has a supporting line at every point and lies above all of them. Turn that round: the function is the upper envelope of its tangents. Nothing is lost by discarding the curve and keeping the lines.

A line is two numbers, a slope and an intercept, and the tangents of a convex function have one intercept per slope. So the whole function is encoded in a single function of the slope — and that encoding is invertible.

The move is worth recognising as a type before the details arrive. Describing an object by the things that touch it rather than by the things it contains is a standard exchange: a convex set by its supporting hyperplanes, a curve by its tangent lines, a lattice by the planes it lies on. In each case the description is dual, the same information is present, and the operations that are hard on one side are easy on the other.

The definition #

For a convex $f$ and a slope $p$, define

$$f^*(p) = \sup_x \big(px - f(x)\big).$$

Read geometrically: take the line through the origin of slope $p$, and ask how far below the curve it can be pushed while still touching. The answer is the negative of the tangent line’s intercept, and $f^*(p)$ is that gap.

So $f^*$ tabulates the intercepts of the tangents, indexed by their slopes. The sign convention is chosen so that the result comes out convex and positive in the standard cases, and nothing conceptual depends on it. The maximisation is over $x$ and produces a function of $p$, which is why the transform swaps a variable for a slope.

Two examples fix it. For $f(x) = x^2/2$, the supremum of $px - x^2/2$ is found by differentiating: $p - x = 0$, so $x = p$, and the value is $p^2 - p^2/2 = p^2/2$. The function is its own transform, and it is essentially the only one that is.

For $f(x) = e^x$, differentiating $px - e^x$ gives $p = e^x$, so $x = \log p$, and the value is $p\log p - p$ — defined only for $p > 0$, since a line of non-positive slope never touches the exponential. That expression is the entropy of information theory and of statistical mechanics, arriving here as the conjugate of the exponential, which is where it comes from.

Why it undoes itself #

The property that makes the transform worth having is that applying it twice returns the original — for convex functions, and only for them.

$$f^{**} = f \quad \text{when } f \text{ is convex.}$$

The reason is the envelope picture. $f^*$ records the tangent lines; $f^{**}$ reconstructs the upper envelope of the lines $f^*$ records; and a convex function is that envelope, which is the previous rung’s content.

For a function that is not convex, $f^{**}$ is its convex hull — the largest convex function below it. So the transform is not an involution on all functions; it is an involution on convex ones, and on the others it projects.

That projection is informative rather than a defect. It says exactly what a non-convex function looks like from the point of view of tangent lines: the dips are invisible, because no supporting line touches them, and what survives is the hull.

The information lost is precisely measurable. A non-convex function differs from its hull on the intervals where it bulges above the hull, and the transform is blind to those and to nothing else. So $f - f^{**}$ is a complete account of what the tangent lines cannot see, and it is zero exactly when the function is convex — which is a restatement of the involution property and is a more useful form of it.

A table of transforms #

Working out a few by hand is worth more than the general theory, because the pattern is visible in them and not in the definition.

The second row is the one to keep. The powers transform into powers with conjugate exponents, the pair satisfying $1/a + 1/b = 1$ — which is exactly the pair appearing in Hölder’s inequality, and Hölder’s inequality is Fenchel’s applied to those two functions. A named inequality with a mysterious condition on its exponents turns out to be one transform, and the condition is the statement that the exponents are conjugate.

The last row shows the extreme behaviour. A function that is a line has a transform concentrated at one slope and infinite elsewhere — all its information is one number, and the transform says so.

What the transform does to operations #

The transform’s value is that it converts operations into easier ones, and there are three worth knowing.

Addition becomes infimal convolution. The transform of $f + g$ is not the sum of the transforms; it is their infimal convolution, $\inf_q (f^*(q) + g^*(p-q))$ — the cheapest way of splitting a slope between the two functions. Conversely the transform of an infimal convolution is a sum, so an awkward operation on one side is an easy one on the other. That is the same trade the Fourier transform makes with ordinary convolution, and the analogy is close enough that infimal convolution is sometimes called tropical convolution.

Scaling inverts. $(\lambda f)^*(p) = \lambda f^*(p/\lambda)$, so scaling a function scales its transform in both coordinates.

And a minimum becomes a value at zero. $f^*(0) = \sup_x(-f(x)) = -\inf_x f(x)$, so the transform at zero is the negative of the minimum. Every optimisation is a single evaluation on the other side, which is the sense in which the transform is the abstract form of duality — the whole difficulty having been moved into computing the transform, which is where it stays.

That last identity is the connection to everything else. The dual of a convex optimisation problem is built from the transforms of its ingredients, and weak duality — the dual bounds the primal — is the inequality $f(x) + f^*(p) \ge px$, which holds by the definition of a supremum and is called Fenchel’s inequality.

Where it is used #

The transform appears in three subjects with three names and one meaning.

Mechanics. Passing from the Lagrangian, a function of position and velocity, to the Hamiltonian, a function of position and momentum, is the Legendre transform in the velocity variable. Momentum is the slope — it is the derivative of the Lagrangian with respect to velocity, which is exactly what the transform’s variable is — and the transform is what makes the equations first-order rather than second, at the price of doubling the number of them.

Thermodynamics. Free energy is the transform of internal energy with respect to entropy, temperature being the slope. The whole family of thermodynamic potentials — Helmholtz, Gibbs, enthalpy — is a family of transforms in different variables, and the relations between them are the transform’s algebra.

And large deviations. The rate function governing the probability of a rare average is the transform of the cumulant generating function. That is Cramér’s theorem: the chance that an average of $n$ independent samples lands near an unlikely value $a$ falls like $e^{-nI(a)}$, and $I$ is the transform of the logarithm of the moment generating function. It is why an exponentially small probability has a convex exponent: the exponent is a transform, and transforms are convex whatever they came from. The deviation bounds this collection proves by other means are that theorem’s crude form, and the transform is what makes them exact.

That last is a genuinely useful fact. $f^*$ is convex for any $f$, convex or not, because it is a supremum of linear functions of $p$. Convexity is manufactured by the transform, which is why rate functions, free energies and Hamiltonians are convex without anybody having to arrange it.

Fenchel’s inequality is worth stating separately from its proof, because the proof is a triviality and the statement is not. By definition $f^*(p) \ge px - f(x)$ for every $x$, since the supremum is at least any particular value. Rearranged, that is

$$f(x) + f^*(p) \ge px$$

for every $x$ and every $p$, with equality exactly when $p$ is a supporting slope at $x$.

That is the whole of weak duality, in one line. In an optimisation problem the primal variable is $x$, the dual variable is $p$, the two objectives are the two sides, and the inequality says each bounds the other. Equality holds exactly at complementary slackness, which is the condition the assignment problem’s prices satisfy — and there it looked like a combinatorial coincidence and here it is a definition.

What it costs #

Non-differentiable points and flat pieces swap. A kink in $f$ — a point where the slope jumps from $p_1$ to $p_2$ — becomes a straight piece of $f^*$ between $p_1$ and $p_2$, because every slope in that range is supported at the same place; and a straight piece of $f$ becomes a kink in $f^*$, by the same reading run backwards. So the transform is not smoothness-preserving in either direction, and any argument assuming differentiability on both sides is assuming something extra.

The domain can shrink. The exponential is defined on the whole line and its transform only on the positive slopes, because no line of non-positive slope supports it. The transform’s domain is the set of slopes the function actually attains, which can be an interval, a half-line, or a single point — and reading a function by its slopes is therefore reading it on a different set from the one it lives on.

The transform of a transform is cheap and the transform itself is not. Computing $f^*$ at one slope is an optimisation, so tabulating it is many optimisations. That is why the transform is a theoretical device rather than a numerical one: it converts one hard problem into another of the same difficulty, and its value is in what it proves rather than in what it computes.

And the supremum can be infinite. For a function growing slower than linearly, the supremum defining the transform is infinite at large slopes, and the transform takes the value $+\infty$ there. Working with functions allowed to be infinite is the standard convention, and it is a convention that has to be adopted before the theory is tidy.

What the loss of information means #

The projection onto the convex hull is worth taking seriously as a modelling statement rather than as a technicality.

In thermodynamics the non-convex parts of an energy function correspond to unstable states, and the convex hull is what a real system exhibits — the flat piece of the hull is coexistence, where the system splits into two states — ice and water, liquid and vapour — rather than sitting at an unstable intermediate. So the transform’s loss of information is physically correct: the states it discards are the ones that do not occur.

That is the Maxwell construction, and it is one of the places where a mathematical operation’s failure to be invertible turns out to be the point.

The van der Waals equation of state is the standard instance. Below the critical temperature it predicts a region where pressure rises with volume, which is mechanically unstable and does not occur; the free energy there is non-convex, its convex hull replaces the offending stretch by a straight segment, and the segment is the liquid–gas coexistence. A physical impossibility and a mathematical non-convexity are the same thing seen twice, and the transform is what identifies them with each other.

The same reading applies elsewhere. In optimisation, the dual problem’s optimum equals the primal’s convex hull’s, so a duality gap for a non-convex problem is exactly the height of the bump the transform removed. The gap is not a defect of the method; it is the distance between the problem and its hull.

Where the name comes from, and why it is misleading #

Legendre introduced the construction in 1787, in work on differential equations, as a change of variables: replace $y'$ by a new variable and the equation simplifies.

That is not what it is. A change of variables is a relabelling and this is not — it produces a different function on a different space, and the relationship between them is a duality rather than a substitution. Reading it as a change of variables is the standard first misunderstanding, and it produces the standard confusion about why the transform is its own inverse: a change of variables applied twice returns the original by definition, and here it is a theorem, true only for convex functions.

Fenchel gave it the modern form in the 1940s, working in convex analysis, with the supremum definition that makes sense for functions that are not differentiable. That version is the one everything above uses, and it is why the transform is often called the Legendre–Fenchel transform.

The difference between the two is worth being precise about. Legendre’s version needs $f'$ to be invertible, so it needs strict convexity and differentiability; Fenchel’s needs neither, and where Legendre’s applies the two agree. The generalisation is not a technical convenience: functions with kinks are the normal case in optimisation, and a transform that could not handle them would be unusable there.

What the pictures cannot show #

The supremum is computed by search. Every value of the transform in the figures is obtained by scanning two thousand points of the interval and taking the largest. That is exact enough to check against a closed form and it is not the definition, which is a supremum over an unbounded domain.

One variable again. The transform in several variables sends a function of a vector to a function of a vector of slopes, and the supporting objects are hyperplanes. The picture of a line touching a curve is the case where the drawing exists, and every application named above is in many variables.

Neither the convex hull nor the projection is drawn. The section on lost information is about $f^{**}$ for a non-convex $f$, and the figure showing a non-convex function shows its minima rather than its hull. Drawing the hull would need a second curve laid over the first, which is a figure this family does not have.

And the involution is checked at four points. Transforming twice and comparing is done at four values of $x$, to a tolerance. The theorem is that the two functions agree everywhere, and the check is a sample.

Where the ladder goes next #

The last rung of this pass asks what happens when convexity fails, and what is left: where the guarantee stops.

Named here as debts. Fenchel duality in its general form, which is the transform applied to a constrained problem and is the machinery behind most of convex optimisation. And the infimal convolution as an operation in its own right, mentioned above and not developed.

Sideways, the supporting lines the transform tabulates are the previous rung’s, the certificate a dual solution provides is the same duality in a finite setting, the description of an object by what touches it is the same exchange the lifting map makes, and the chord definition the whole anchor starts from is the first rung.

What is worth carrying away #

A description of an object by its tangents is a description of the object, when the object is convex — and the change of description turns hard operations into easy ones.

The Legendre transform swaps a variable for a slope, sends addition to infimal convolution, sends minimisation to evaluation at zero, and undoes itself. Every one of those is a consequence of one picture: a convex function is the upper envelope of its tangent lines, so the lines carry all the information.

The habit worth taking is to ask what an object looks like from its supporting objects. For a convex set that is its supporting hyperplanes, for a convex function its tangents, and in both cases the dual description is the one in which the natural operations become simple.

One consequence is worth stating plainly, since it is what makes the transform worth learning rather than admiring. An operation that is awkward on functions — combining two of them by taking, for each total, the best split between them — becomes ordinary addition on the transformed side. Hard operations turned into easy ones by a change of description is the whole return on the work of setting the description up.