The Conjugate Function

f^(y) is the largest gap between a line of slope y and the graph of f — a construction that returns a convex function whatever you feed it.

The idea

The conjugate $f^{*}$ of a function $f$ records, for each slope $y$, the largest gap between the line of slope $y$ through the origin and the graph of $f$.

Fix $y$ and write the line as $yx$. At each $x$ the number $y x - f(x)$ is the height of the line above the graph — negative wherever the graph is on top — and the conjugate is the largest value of this gap:

$f^{*}(y) = \sup_{x} \big(y x - f(x)\big).$

The same number appears geometrically. Slide a line of slope $y$, lying entirely below the graph, upward until it first touches, at a point $x^{}$. This supporting line meets the vertical axis at height $-f^{}(y)$: raising it any further would cut the graph, which is precisely the statement that the largest gap has been used up.

The supremum need not be finite. The domain of $f^{*}$ is the set of slopes for which it is, and it can be smaller than the domain of $f$: a slope steeper than any the graph attains lets $y x - f(x)$ grow without bound.

Ways to work on it

• Walkthrough. The definition, its supporting-line picture, and the conjugate computed for a few standard functions.
• Proof: the conjugate is always convex. f^ is a pointwise supremum of straight lines in y, so it is convex for every f.
• Practice. Compute the conjugate of a standard function from scratch.
• Hardest. Conjugate the strictly convex quadratic 1/2x^ Qx on ℝ^n, then evaluate it.

Not sure where to start? Take the ten-question placement test.