Convex conjugate

In mathematics and mathematical optimization, the convex conjugate of a function is a generalization of the Legendre transformation which applies to non-convex functions. It is also known as Legendre–Fenchel transformation, Fenchel transformation, or Fenchel conjugate (after Adrien-Marie Legendre and Werner Fenchel). The convex conjugate is widely used for constructing the dual problem in optimization theory, thus generalizing Lagrangian duality.

Let ${\displaystyle X}$ be a real topological vector space and let ${\displaystyle X^{*}}$ be the dual space to ${\displaystyle X}$. Denote by

${\displaystyle \langle \cdot ,\cdot \rangle :X^{*}\times X\to \mathbb {R} }$

the canonical dual pairing, which is defined by ${\displaystyle \left\langle x^{*},x\right\rangle \mapsto x^{*}(x).}$

For a function ${\displaystyle f:X\to \mathbb {R} \cup \{-\infty ,+\infty \}}$ taking values on the extended real number line, its convex conjugate is the function

${\displaystyle f^{*}:X^{*}\to \mathbb {R} \cup \{-\infty ,+\infty \}}$

whose value at ${\displaystyle x^{*}\in X^{*}}$ is defined to be the supremum:

${\displaystyle f^{*}\left(x^{*}\right):=\sup \left\{\left\langle x^{*},x\right\rangle -f(x)~\colon ~x\in X\right\},}$

or, equivalently, in terms of the infimum:

${\displaystyle f^{*}\left(x^{*}\right):=-\inf \left\{f(x)-\left\langle x^{*},x\right\rangle ~\colon ~x\in X\right\}.}$

This definition can be interpreted as an encoding of the convex hull of the function's epigraph in terms of its supporting hyperplanes.^[1]

For more examples, see § Table of selected convex conjugates.

• The convex conjugate of an affine function ${\displaystyle f(x)=\left\langle a,x\right\rangle -b}$ is $${\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}b,&x^{*}=a\\+\infty ,&x^{*}\neq a.\end{cases}}}$$
• The convex conjugate of a power function ${\displaystyle f(x)={\frac {1}{p}}|x|^{p},1<p<\infty }$ is $${\displaystyle f^{*}\left(x^{*}\right)={\frac {1}{q}}|x^{*}|^{q},1<q<\infty ,{\text{where}}{\tfrac {1}{p}}+{\tfrac {1}{q}}=1.}$$
• The convex conjugate of the absolute value function ${\displaystyle f(x)=\left|x\right|}$ is $${\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}0,&\left|x^{*}\right|\leq 1\\\infty ,&\left|x^{*}\right|>1.\end{cases}}}$$
• The convex conjugate of the exponential function ${\displaystyle f(x)=e^{x}}$ is $${\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}x^{*}\ln x^{*}-x^{*},&x^{*}>0\\0,&x^{*}=0\\\infty ,&x^{*}<0.\end{cases}}}$$

The convex conjugate and Legendre transform of the exponential function agree except that the ___domain of the convex conjugate is strictly larger as the Legendre transform is only defined for positive real numbers.

See this article for example.

Let F denote a cumulative distribution function of a random variable X. Then (integrating by parts), $${\displaystyle f(x):=\int _{-\infty }^{x}F(u)\,du=\operatorname {E} \left[\max(0,x-X)\right]=x-\operatorname {E} \left[\min(x,X)\right]}$$ has the convex conjugate $${\displaystyle f^{*}(p)=\int _{0}^{p}F^{-1}(q)\,dq=(p-1)F^{-1}(p)+\operatorname {E} \left[\min(F^{-1}(p),X)\right]=pF^{-1}(p)-\operatorname {E} \left[\max(0,F^{-1}(p)-X)\right].}$$

A particular interpretation has the transform $${\displaystyle f^{\text{inc}}(x):=\arg \sup _{t}t\cdot x-\int _{0}^{1}\max\{t-f(u),0\}\,du,}$$ as this is a nondecreasing rearrangement of the initial function f; in particular, ${\displaystyle f^{\text{inc}}=f}$ for f nondecreasing.

The convex conjugate of a closed convex function is again a closed convex function. The convex conjugate of a polyhedral convex function (a convex function with polyhedral epigraph) is again a polyhedral convex function.

Declare that ${\displaystyle f\leq g}$ if and only if ${\displaystyle f(x)\leq g(x)}$ for all ${\displaystyle x.}$ Then convex-conjugation is order-reversing, which by definition means that if ${\displaystyle f\leq g}$ then ${\displaystyle f^{*}\geq g^{*}.}$

For a family of functions ${\displaystyle \left(f_{\alpha }\right)_{\alpha }}$ it follows from the fact that supremums may be interchanged that

${\displaystyle \left(\inf _{\alpha }f_{\alpha }\right)^{*}(x^{*})=\sup _{\alpha }f_{\alpha }^{*}(x^{*}),}$

and from the max–min inequality that

${\displaystyle \left(\sup _{\alpha }f_{\alpha }\right)^{*}(x^{*})\leq \inf _{\alpha }f_{\alpha }^{*}(x^{*}).}$

The convex conjugate of a function is always lower semi-continuous. The biconjugate ${\displaystyle f^{**}}$ (the convex conjugate of the convex conjugate) is also the closed convex hull, i.e. the largest lower semi-continuous convex function with ${\displaystyle f^{**}\leq f.}$ For proper functions ${\displaystyle f,}$

${\displaystyle f=f^{**}}$ if and only if ${\displaystyle f}$ is convex and lower semi-continuous, by the Fenchel–Moreau theorem.

For any function f and its convex conjugate f *, Fenchel's inequality (also known as the Fenchel–Young inequality) holds for every ${\displaystyle x\in X}$ and ${\displaystyle p\in X^{*}}$:

${\displaystyle \left\langle p,x\right\rangle \leq f(x)+f^{*}(p).}$

Furthermore, the equality holds only when ${\displaystyle p\in \partial f(x)}$. The proof follows from the definition of convex conjugate: ${\displaystyle f^{*}(p)=\sup _{\tilde {x}}\left\{\langle p,{\tilde {x}}\rangle -f({\tilde {x}})\right\}\geq \langle p,x\rangle -f(x).}$

For two functions ${\displaystyle f_{0}}$ and ${\displaystyle f_{1}}$ and a number ${\displaystyle 0\leq \lambda \leq 1}$ the convexity relation

${\displaystyle \left((1-\lambda )f_{0}+\lambda f_{1}\right)^{*}\leq (1-\lambda )f_{0}^{*}+\lambda f_{1}^{*}}$

holds. The ${\displaystyle {*}}$ operation is a convex mapping itself.

The infimal convolution (or epi-sum) of two functions ${\displaystyle f}$ and ${\displaystyle g}$ is defined as

${\displaystyle \left(f\operatorname {\Box } g\right)(x)=\inf \left\{f(x-y)+g(y)\mid y\in \mathbb {R} ^{n}\right\}.}$

Let ${\displaystyle f_{1},\ldots ,f_{m}}$ be proper, convex and lower semicontinuous functions on ${\displaystyle \mathbb {R} ^{n}.}$ Then the infimal convolution is convex and lower semicontinuous (but not necessarily proper),^[2] and satisfies

${\displaystyle \left(f_{1}\operatorname {\Box } \cdots \operatorname {\Box } f_{m}\right)^{*}=f_{1}^{*}+\cdots +f_{m}^{*}.}$

The infimal convolution of two functions has a geometric interpretation: The (strict) epigraph of the infimal convolution of two functions is the Minkowski sum of the (strict) epigraphs of those functions.^[3]

If the function ${\displaystyle f}$ is differentiable, then its derivative is the maximizing argument in the computation of the convex conjugate:

${\displaystyle f^{\prime }(x)=x^{*}(x):=\arg \sup _{x^{*}}{\langle x,x^{*}\rangle }-f^{*}\left(x^{*}\right)}$ and

${\displaystyle f^{{*}\prime }\left(x^{*}\right)=x\left(x^{*}\right):=\arg \sup _{x}{\langle x,x^{*}\rangle }-f(x);}$

hence

${\displaystyle x=\nabla f^{*}\left(\nabla f(x)\right),}$

${\displaystyle x^{*}=\nabla f\left(\nabla f^{*}\left(x^{*}\right)\right),}$

and moreover

${\displaystyle f^{\prime \prime }(x)\cdot f^{{*}\prime \prime }\left(x^{*}(x)\right)=1,}$

${\displaystyle f^{{*}\prime \prime }\left(x^{*}\right)\cdot f^{\prime \prime }\left(x(x^{*})\right)=1.}$

If for some ${\displaystyle \gamma >0,}$ ${\displaystyle g(x)=\alpha +\beta x+\gamma \cdot f\left(\lambda x+\delta \right)}$, then

${\displaystyle g^{*}\left(x^{*}\right)=-\alpha -\delta {\frac {x^{*}-\beta }{\lambda }}+\gamma \cdot f^{*}\left({\frac {x^{*}-\beta }{\lambda \gamma }}\right).}$

Let ${\displaystyle A:X\to Y}$ be a bounded linear operator. For any convex function ${\displaystyle f}$ on ${\displaystyle X,}$

${\displaystyle \left(Af\right)^{*}=f^{*}A^{*}}$

where

${\displaystyle (Af)(y)=\inf\{f(x):x\in X,Ax=y\}}$

is the preimage of ${\displaystyle f}$ with respect to ${\displaystyle A}$ and ${\displaystyle A^{*}}$ is the adjoint operator of ${\displaystyle A.}$^[4]

A closed convex function ${\displaystyle f}$ is symmetric with respect to a given set ${\displaystyle G}$ of orthogonal linear transformations,

${\displaystyle f(Ax)=f(x)}$ for all ${\displaystyle x}$ and all ${\displaystyle A\in G}$

if and only if its convex conjugate ${\displaystyle f^{*}}$ is symmetric with respect to ${\displaystyle G.}$

The following table provides Legendre transforms for many common functions as well as a few useful properties.^[5]

${\displaystyle g(x)}$	${\displaystyle \operatorname {dom} (g)}$	${\displaystyle g^{*}(x^{*})}$	${\displaystyle \operatorname {dom} (g^{*})}$
${\displaystyle f(ax)}$ (where ${\displaystyle a\neq 0}$)	${\displaystyle X}$	${\displaystyle f^{*}\left({\frac {x^{*}}{a}}\right)}$	${\displaystyle X^{*}}$
${\displaystyle f(x+b)}$	${\displaystyle X}$	${\displaystyle f^{*}(x^{*})-\langle b,x^{*}\rangle }$	${\displaystyle X^{*}}$
${\displaystyle af(x)}$ (where ${\displaystyle a>0}$)	${\displaystyle X}$	${\displaystyle af^{*}\left({\frac {x^{*}}{a}}\right)}$	${\displaystyle X^{*}}$
${\displaystyle \alpha +\beta x+\gamma \cdot f(\lambda x+\delta )}$	${\displaystyle X}$	${\displaystyle -\alpha -\delta {\frac {x^{*}-\beta }{\lambda }}+\gamma \cdot f^{*}\left({\frac {x^{*}-\beta }{\gamma \lambda }}\right)\quad (\gamma >0)}$	${\displaystyle X^{*}}$
${\displaystyle {\frac {|x|^{p}}{p}}}$ (where ${\displaystyle p>1}$)	${\displaystyle \mathbb {R} }$	${\displaystyle {\frac {|x^{*}|^{q}}{q}}}$ (where ${\displaystyle {\frac {1}{p}}+{\frac {1}{q}}=1}$)	${\displaystyle \mathbb {R} }$
${\displaystyle {\frac {-x^{p}}{p}}}$ (where ${\displaystyle 0<p<1}$)	${\displaystyle \mathbb {R} _{+}}$	${\displaystyle {\frac {-(-x^{*})^{q}}{q}}}$ (where ${\displaystyle {\frac {1}{p}}+{\frac {1}{q}}=1}$)	${\displaystyle \mathbb {R} _{--}}$
${\displaystyle {\sqrt {1+x^{2}}}}$	${\displaystyle \mathbb {R} }$	${\displaystyle -{\sqrt {1-(x^{*})^{2}}}}$	${\displaystyle [-1,1]}$
${\displaystyle -\log(x)}$	${\displaystyle \mathbb {R} _{++}}$	${\displaystyle -(1+\log(-x^{*}))}$	${\displaystyle \mathbb {R} _{--}}$
${\displaystyle e^{x}}$	${\displaystyle \mathbb {R} }$	${\displaystyle {\begin{cases}x^{*}\log(x^{*})-x^{*}&{\text{if }}x^{*}>0\\0&{\text{if }}x^{*}=0\end{cases}}}$	${\displaystyle \mathbb {R} _{+}}$
${\displaystyle \log \left(1+e^{x}\right)}$	${\displaystyle \mathbb {R} }$	${\displaystyle {\begin{cases}x^{*}\log(x^{*})+(1-x^{*})\log(1-x^{*})&{\text{if }}0<x^{*}<1\\0&{\text{if }}x^{*}=0,1\end{cases}}}$	${\displaystyle [0,1]}$
${\displaystyle -\log \left(1-e^{x}\right)}$	${\displaystyle \mathbb {R} _{--}}$	${\displaystyle {\begin{cases}x^{*}\log(x^{*})-(1+x^{*})\log(1+x^{*})&{\text{if }}x^{*}>0\\0&{\text{if }}x^{*}=0\end{cases}}}$	${\displaystyle \mathbb {R} _{+}}$

• Dual problem
• Fenchel's duality theorem
• Legendre transformation
• Young's inequality for products

• Arnol'd, Vladimir Igorevich (1989). Mathematical Methods of Classical Mechanics (Second ed.). Springer. ISBN 0-387-96890-3. MR 0997295.
• Rockafellar, R. Tyrrell; Wets, Roger J.-B. (26 June 2009). Variational Analysis. Grundlehren der mathematischen Wissenschaften. Vol. 317. Berlin New York: Springer Science & Business Media. ISBN 9783642024313. OCLC 883392544.
• Rockafellar, R. Tyrell (1970). Convex Analysis. Princeton: Princeton University Press. ISBN 0-691-01586-4. MR 0274683.

• Touchette, Hugo (2014-10-16). "Legendre-Fenchel transforms in a nutshell" (PDF). Archived from the original (PDF) on 2017-04-07. Retrieved 2017-01-09.

• Touchette, Hugo (2006-11-21). "Elements of convex analysis" (PDF). Archived from the original (PDF) on 2015-05-26. Retrieved 2008-03-26.

• Ellerman, David Patterson (1995-03-21). "Chapter 12: Parallel Addition, Series-Parallel Duality, and Financial Mathematics". Intellectual Trespassing as a Way of Life: Essays in Philosophy, Economics, and Mathematics (PDF). The worldly philosophy: studies in intersection of philosophy and economics. Rowman & Littlefield Publishers, Inc. pp. 237–268. ISBN 0-8476-7932-2. Archived (PDF) from the original on 2016-03-05. Retrieved 2019-08-09. Series G - Reference, Information and Interdisciplinary Subjects Series [1] (271 pages)

• Ellerman, David Patterson (May 2004) [1995-03-21]. "Introduction to Series-Parallel Duality" (PDF). University of California at Riverside. CiteSeerX 10.1.1.90.3666. Archived from the original on 2019-08-10. Retrieved 2019-08-09. [2] (24 pages)