 Convex conjugate

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 iswhere $p\cdot x$ is the dot product and $\mathrm{dom}f=\{x:f(x)<+\infty \}$ is the effective domain. An infinite value of $f$ excludes that input from the supremum. The value $f^{\ast }(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 Boyd and Vandenberghe, Convex Optimization (2004), §3.3.1.

The best lower bound with a prescribed slope. Whenever $f^{\ast }(p)$ is finite, the affine functionis an affine minorant of $f$. Indeed, an affine function $p\cdot x+b$ lies below $f$ everywhere exactly when $b\le {\inf }_x(f(x)-p\cdot x)=-f^{\ast }(p)$. Thus $-f^{\ast }(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.

A quadratic, computed by completing the square. For the convex quadratic function $f(x)=x^2/2$,Consequently $f^{\ast }(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^{\ast }(p)=-p^2/2$. For example, $p=2$ gives $f^{\ast }(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.

A corner turns into a constraint on slopes. For the absolute value $f(x)=|x|$, if $|p|\le 1$ then $px-|x|\le 0$, 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\ge 0$ maximizes, and for $p=-1$ every $x\le 0$ maximizes. The corner's many supporting slopes are exactly the subdifferential $\partial f(0)=[-1,1]$.

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^{\ast }(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.

The convex conjugate, also known as the Legendre-Fenchel transform, is a concept in convex analysis and optimization that is used to transform a convex function into another function.