= Convex conjugate
{title2=$f^*(p)=\sup_x(p\cdot x-f(x))$}
{wiki}
= Legendre-Fenchel transform
{c}
{synonym}
= Fenchel conjugate
{c}
{synonym}
= Legendre transformation
{c}
{synonym}
= Legendre transform
{c}
{synonym}
The <convex conjugate> records a <function> using slopes rather than input positions. Let $f:\mathbb R^n\to\mathbb R\cup\{+\infty\}$ be a <proper extended-real function>: it is finite somewhere and never takes $-\infty$. Its <convex conjugate> is
$$
f^*(p)=\sup_{x\in\mathbb R^n}\{p\cdot x-f(x)\}=\sup_{x\in\operatorname{dom}f}\{p\cdot x-f(x)\},\qquad p\in\mathbb R^n,
$$
where $p\cdot x$ is the <dot product> and $\operatorname{dom}f=\{x:f(x)<+\infty\}$ is the <effective domain>. An infinite value of $f$ excludes that input from the <supremum>. The value $f^*(p)$ can be $+\infty$, but cannot be $-\infty$ because an input with finite $f(x)$ supplies a finite lower bound.
The <convex conjugate> is automatically a <convex function>, even when $f$ is not <convex>: each fixed input gives an <affine function> $p\mapsto p\cdot x-f(x)$, and their <supremum> is <convex>. It is also <lower semicontinuous>. It need not be proper: for $f(x)=-x^2$ on $\mathbb R$, $px-f(x)=px+x^2$ is unbounded above for every $p$. The definition and the automatic <convexity> are discussed in https://stanford.edu/~boyd/cvxbook/bv_cvxbook.pdf#page=105[Boyd and Vandenberghe, Convex Optimization (2004), §3.3.1].
\b[The best lower bound with a prescribed slope.] Whenever $f^*(p)$ is finite, the <affine function>
$$
\ell_p(x)=p\cdot x-f^*(p)
$$
is an <affine minorant> of $f$. Indeed, an <affine function> $p\cdot x+b$ lies below $f$ everywhere exactly when $b\leq\inf_x(f(x)-p\cdot x)=-f^*(p)$. Thus $-f^*(p)$ is the largest possible intercept at slope $p$. The <convex conjugate> trades positions for slopes: $x$ specifies where to inspect $f$, whereas $p$ specifies which global <affine minorant> to use. Taking the <supremum> over all these <affine minorants> produces the <biconjugate>; the <Fenchel-Moreau theorem> says this recovers a <proper convex function> when it is <lower semicontinuous>.
\b[A quadratic, computed by completing the square.] For the <convex quadratic function> $f(x)=x^2/2$,
$$
px-\frac{x^2}{2}=\frac{p^2}{2}-\frac{(x-p)^2}{2}.
$$
Consequently $f^*(p)=p^2/2$, and the unique maximizing input is $x=p$. The <affine minorant> $\ell_p(x)=px-p^2/2$ is the <tangent line> at $(p,p^2/2)$: its slope is $p$ and its intercept is $-f^*(p)=-p^2/2$. For example, $p=2$ gives $f^*(2)=2$ and the <tangent line> $2x-2$, touching at $(2,2)$. This is the same curve described either by its point values or by the intercepts of its <tangent lines>.
\Image[/convex-conjugate-support-lines.png]
{title=The <convex conjugate> determines the intercept of each <tangent line> of a <convex quadratic function>}
{description=For the <convex quadratic function> $f(x)=x^2/2$, the colored <tangent lines> have slopes $p=-1,0,2$ and touch at $x=p$. The right panel plots the <convex conjugate> $f^*(p)=p^2/2$ and marks the matching slope-value pairs. The highlighted <tangent line> $2x-2$ has intercept $-f^*(2)=-2$.}
\b[A corner turns into a constraint on slopes.] For the <absolute value> $f(x)=|x|$, if $|p|\leq1$ then $px-|x|\leq0$, with value zero at $x=0$. If $p>1$, taking $x\to+\infty$ makes $(p-1)x\to+\infty$; if $p<-1$, taking $x\to-\infty$ does the same. Therefore its <convex conjugate> is zero on $[-1,1]$ and $+\infty$ outside: it is the <indicator functional of a constraint set> for this interval. For $|p|<1$ the unique maximizing input is zero; for $p=1$ every $x\geq0$ maximizes, and for $p=-1$ every $x\leq0$ maximizes. The corner's many supporting slopes are exactly the <subdifferential> $\partial f(0)=[-1,1]$.
\b[A supremum need not be attained.] For a <differentiable> <convex function> finite on all of $\mathbb R^n$, an input maximizes $p\cdot x-f(x)$ exactly when $p=\nabla f(x)$. If $f$ is <strictly convex>, there is at most one such input; existence is a separate issue. For the <exponential function> $f(x)=e^x$, the <derivative> is positive. At $p>0$, solving $p=e^x$ gives $x=\log p$ and $f^*(p)=p\log p-p$. At $p=0$, the <supremum> of $-e^x$ is zero as $x\to-\infty$, with no maximizing input. At $p<0$, $px-e^x\to+\infty$ as $x\to-\infty$. Thus a <strictly convex> <differentiable> <function> can have both unattained finite conjugate values and infinite conjugate values.
Back to article page
