Convex conjugate ($f^{\ast }(p)={\sup }_x(p\cdot x-f(x))$)

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.

For an increasing concave utility on positive wealth, its utility conjugate uses the indicated supremum and is a convex function of the positive price variable. If $F(x)=-U(x)$ on positive $x$, extended by infinity elsewhere, then $\hat{U}(y)=F^{\ast }(-y)$. Under the Inada conditions its optimizer is the inverse marginal utility, and its derivative is the negative of that optimizer. The sign convention is part of the definition.

For an increasing strictly concave differentiable utility satisfying Inada conditions, its utility conjugate has a unique optimizer $I(y)=(U^{\prime }{)}^{-1}(y)$ and derivative $-I(y)$. The dual is strictly decreasing and strictly convex. Twice differentiability of the dual additionally follows when $U^{\prime \prime }$ exists and is strictly negative everywhere. Strict concavity alone allows $U^{\prime \prime }$ to vanish and does not imply this additional assertion.

For $f(x)=x\log x$ on $x>0$, strict convexity and the stationary condition $p=1+\log x$ give the displayed convex conjugate for every real $p$. Biconjugation recovers $f$ on its original positive domain. Its closed extended-real extension has value zero at zero and infinity on negative arguments.

The biconjugate of $f$ is the convex conjugate of its convex conjugate:It is the supremum of all affine minorants. For a proper function with an affine minorant, the Fenchel-Moreau theorem identifies it with the closed convex envelope; a proper lower semicontinuous convex function equals its biconjugate.

If $g(x)=\lambda f(x-x_0)-\mu$ with $\lambda >0$, substitution into the supremum defining the convex conjugate givesThe positivity of $\lambda$ allows it to pass through the supremum without reversing it. Negative scaling need not obey this rule for the convex conjugate, even when a formal stationary-value transform does.

For a differentiable strictly concave function $f$ whose derivative is a bijection of $\mathbb{R}$, defineThe unique minimizing point is $h(z)$, and $g^{\prime }=h$ follows by comparing minimizers at adjacent arguments, even when $h$ is not differentiable. This dual is concave and equals $-(-f{)}^{\ast }(-z)$ in terms of the convex conjugate. If $f^{\prime \prime }<0$, then $g^{\prime \prime }=1/f^{\prime \prime }(h)$. For $f(s)=cs-s^2/2$, $g(z)=-(z-c{)}^2/2$.

The lower conjugate uses an infimum, unlike the supremum defining a convex conjugate. For any $F$, $F_{\ast }(\tau )=-(-F{)}^{\ast }(-\tau )$ and $F(e)\le \tau :e-F_{\ast }(\tau )$. The inequality is informative only when the lower conjugate is finite. If the infimum is attained uniquely and the dual is differentiable, $D{F}_{\ast }(\tau )$ is its minimizing argument. This sign convention is useful for upper comparison-energy bounds.

The concave biconjugate is an upper envelope of $F$, and equals $F$ for a proper closed concave function under the usual duality hypotheses. It equals $-(-F{)}^{\ast \ast }$ in terms of the ordinary biconjugate. If $e=D{F}_{\ast }(\tau )$, differentiability and concavity of $F_{\ast }$ imply $F_{\ast }(\tau )+F_{\ast \ast }(e)=\tau :e$. For a finite differentiable dual the equality follows because $\tau$ minimizes $s:e-F_{\ast }(s)$.

Suppose $f(0)=0$, $f^{\prime }(0)=c$, $h=(f^{\prime }{)}^{-1}$ is differentiable, and $k_{-}<h^{\prime }/2<k_{+}<0$. Then $h(c)=g(c)=0$ for the concave Legendre dual $g$, andIntegrate the derivative bounds from $c$ to $z$, then integrate $g^{\prime }=h$. Multiplying the first inequality by a negative $z-c$ reverses both comparisons. A bound valid without cases is $|h(z)|\le -2k_{-}|z-c|$.

Maximize $px-x^2/2$ over $|x|\le 1$. The maximizer is $x=\max (-1,\min (p,1))$, giving the displayed Huber loss. The indicator functional of a constraint set is zero on the interval and infinity outside; it is not the zero-one indicator used in measure theory.

A proper lower-semicontinuous convex functional on a real Banach space equals its biconjugate, with the canonical embedding in the bidual understood. One inequality follows from the Fenchel–Young inequality; separation of a point below the closed convex epigraph gives the opposite inequality. This is the closed-convex analogue of recovering a function from all its affine supporting functions.

For a proper extended-real function with an affine minorant, biconjugate gives its greatest lower-semicontinuous convex minorant. Geometric separation of its epigraph turns containing closed half-spaces into affine lower bounds. Vertical half-spaces are recovered by adding multiples of a domain-separating inequality to one fixed affine minorant.

The Fenchel–Young inequality says that every input and every slope obeywhere $f$ is any proper extended-real function and $f^{\ast }$ is its convex conjugate. No convexity assumption on $f$ is needed for this inequality: the defining supremum is at least the particular value $p\cdot x-f(x)$. If either term on the left is $+\infty$, the inequality still holds, but cannot be an equality because the dot product on the right is finite.

For a proper convex function, equality is equivalent to the subgradient conditionTo see this, with $f(x)$ finite, equality says that $x$ attains the supremum defining $f^{\ast }(p)$, so $p\cdot z-f(z)\le p\cdot x-f(x)$ for every $z$. Rearranging gives the subgradient inequality $f(z)\ge f(x)+p\cdot (z-x)$. Geometrically, the affine minorant ${\ell }_p(z)=p\cdot z-f^{\ast }(p)$ touches $f$ at $x$.

If the proper convex function is also closed, meaning its epigraph is a closed set, or equivalently it is lower semicontinuous, thenThe forward implication holds without closedness; the reverse one requires the additional hypothesis in general. Applying the equality criterion to $f^{\ast }$ relates $x\in \partial f^{\ast }(p)$ to $f^{\ast \ast }(x)+f^{\ast }(p)=p\cdot x$, and the Fenchel-Moreau theorem supplies $f^{\ast \ast }=f$ when $f$ is closed. See Bertsekas, Convex Optimization Theory: A Summary, §5.4.1, Proposition 5.4.3 for precisely this distinction.

A concrete failure of the reverse implication occurs for the indicator functional of a constraint set $f$ of the open interval $(-1,1)$. Its convex conjugate is $f^{\ast }(p)=|p|$: the endpoint gives the supremum, even though it is excluded from the interval. At $(x,p)=(1,1)$, $x\in \partial f^{\ast }(p)=\{1\}$, but $f(1)=+\infty$, so equality fails and $\partial f(1)$ is empty. Closing the interval changes the endpoint value and restores equality there.

For the convex quadratic function $f(x)=x^2/2$, the Fenchel–Young inequality is $x^2/2+p^2/2\ge px$, and equality holds exactly when $x=p$. For the absolute value $f(x)=|x|$, finite equality requires $p=\mathrm{sgn}(x)$ at $x\ne 0$, where $\mathrm{sgn}$ is the sign function; at $x=0$ every $p\in [-1,1]$ gives equality. These are exactly the subgradients of the absolute value, including its entire interval of slopes at the corner.

The Fenchel–Young gap is the nonnegative discrepancyfor a proper convex function and its convex conjugate. It can be $+\infty$. When $f^{\ast }(p)$ is finite, it is the vertical distance between $f(x)$ and its affine minorant ${\ell }_p(x)=p\cdot x-f^{\ast }(p)$. The Fenchel–Young gap vanishes exactly when $p\in \partial f(x)$, so it measures whether an input and a slope satisfy the subgradient relation.

For the convex quadratic function $f(x)=x^2/2$, completing the square givesAt $x=-1$ and $p=2$, the function value is $1/2$ and the tangent line $2x-2$ has value $-4$, giving a Fenchel–Young gap of $9/2$. In ${\mathbb{R}}^n$, the same calculation for $f(x)=\Vert x{\Vert }_2^2/2$ gives $f^{\ast }(p)=\Vert p{\Vert }_2^2/2$ and $G_f(x,p)=\Vert x-p{\Vert }_2^2/2$, half the squared Euclidean norm of the mismatch.

An exact optimization error certificate. Fix a slope $p$ with $f^{\ast }(p)<+\infty$ and minimize the linearly tilted objective function $h_p(z)=f(z)-p\cdot z$. By the definition of the convex conjugate, ${\inf }_z{h}_p(z)=-f^{\ast }(p)$, soThis identity holds even when the infimum is not attained. Thus a computed finite Fenchel–Young gap is exactly the error in objective value for this minimization problem. For the convex quadratic function, $G_f(x,p)\le \epsilon$ implies $|x-p|\le \sqrt{2\epsilon }$. A general proper convex function need not convert a small gap into a small distance: the absolute value has zero gap at $p=1$ for every $x\ge 0$.

The Fenchel–Young gap also connects convex analysis to optimal transport. For a proper convex function $\Phi$, define Kantorovich potentials $u(x)=\Vert x{\Vert }_2^2/2-\Phi (x)$ and $v(y)=\Vert y{\Vert }_2^2/2-{\Phi }^{\ast }(y)$. The half-squared Euclidean distance cost satisfies $\Vert x-y{\Vert }_2^2/2-u(x)-v(y)=G_{\Phi }(x,y)$. For a transport plan with finite integrated cost and integrable Kantorovich potentials, integrating this identity gives the difference between transport cost and the potentials' bound. This is the same local subgradient mismatch summed over transported pairs.