Convex conjugate explained

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). It allows in particular for a far reaching generalization of Lagrangian duality.

Definition

Let

X be a real topological vector space and let X ^{*} be the dual space to X . Denote by \langle ⋅ , ⋅ \rangle : X ^{*} x X \to R

the canonical dual pairing, which is defined by

\left( x ^{*,} x \right) \mapsto x ^{*} (x).

For a function

f : X \to R \cup \{ - inf ty, + inf ty \} taking values on the extended real number line, its is the functionf ^{*} : X ^{*} \to R \cup \{ - inf ty, + inf ty \}

whose value at

x ^{*} \in X ^{*} is defined to be the supremum: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:

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]

Examples

For more examples, see .

f(x) = \left\langle a, x \right\rangle - b is f(x) = (1)/(p) |x| ^{p,} 1 < p < inf ty is

• The convex conjugate of the absolute value function

f(x) = \left| x \right| is f(x) = e ^{x} is

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.

Connection with expected shortfall (average value at risk)

See this article for example.

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

Ordering

A particular interpretation has the transform$$f^\backslash text(x):=\; \backslash arg\; \backslash sup\_t\; t\backslash cdot\; x-\backslash int\_0^1\; \backslash max\backslash \; \backslash ,\; du,$$as this is a nondecreasing rearrangement of the initial function f; in particular,

f ^{inc=} f for f nondecreasing.

Properties

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.

Order reversing

Declare that

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

For a family of functions

\left(f _{\alpha\right)} _{\alpha} it follows from the fact that supremums may be interchanged that\left( inf _{\alpha} f ^{*(x} _{\alpha\right)} ^{*)} = \sup _{\alpha} f ^{*(x} _{\alpha} ^{*),}

and from the max–min inequality that

\left(\sup _{\alpha} f ^{*(x} _{\alpha\right)} ^{*)} \le inf _{\alpha} f ^{*(x} _{\alpha} ^{*).}

Biconjugate

The convex conjugate of a function is always lower semi-continuous. The biconjugate

f ^{**} (the convex conjugate of the convex conjugate) is also the closed convex hull, i.e. the largest lower semi-continuous convex function with f ^{**} \le f. For proper functions f, f = f ^{**} if and only if f is convex and lower semi-continuous, by the Fenchel–Moreau theorem.

Fenchel's inequality

For any function and its convex conjugate, Fenchel's inequality (also known as the Fenchel–Young inequality) holds for every

x \in X and \left\langle p,x \right\rangle \le f(x) + f ^{*(p).}

Furthermore, the equality holds only when

p \in \partial f(x) .The proof follows from the definition of convex conjugate: f ^{*(p)} = \sup _{\tilde} \left\{ \langle p,\tilde x \rangle - f(\tilde x) \right\} \ge \langle p,x \rangle - f(x).

Convexity

For two functions

f _{0} and f _{1} and a number 0 \le λ \le 1 the convexity relation \left(( 1-λ ) f _{0} + λ f ^{*} _{1 \right)} \le ( 1-λ ) f ^{*} _{0} + λ f ^{*} _{1}

holds. The

{*} operation is a convex mapping itself.

Infimal convolution

The infimal convolution (or epi-sum) of two functions

f and g is defined as\left( f \operatorname{\Box} g \right)(x) = inf \left\{ f(x - y) + g(y) \mid y \in R ^{n} \right\}.

Let

f _{1,} \ldots, f _{m} be proper, convex and lower semicontinuous functions on R ^{n} . Then the infimal convolution is convex and lower semicontinuous (but not necessarily proper),^[2] and satisfies\left( f _{1} \operatorname{\Box} … \operatorname{\Box} f _{m} \right) ^{*} = f ^{*} _{1} + … + 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]

Maximizing argument

If the function

f is differentiable, then its derivative is the maximizing argument in the computation of the convex conjugate:f ^{\prime(x)} = x ^{*(x):=} \arg\sup _{x ^{*}} {\langle x, x ^{*} \rangle} - f ^{*} \left( x ^{*} \right) andf ^{{*} \prime}\left( x ^{*} \right) = x\left( x ^{*} \right): = \arg\sup _{x} {\langle x, x ^{*} \rangle} - f(x);

hence

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

and moreover

f ^{\prime\prime} (x) ⋅ f ^{{*} \prime\prime}\left( x ^{*} (x) \right) = 1 , f ^{{*} \prime\prime}\left( x ^{*} \right) ⋅ f ^{\prime\prime} \left( x(x ^{*} ) \right) = 1 .

Scaling properties

If for some

\gamma> 0 , g(x) = \alpha + \beta x + \gamma ⋅ f\left( λ x + \delta \right) , then g ^{*} \left( x ^{*} \right) = - \alpha - \delta (x ^{*} - \beta)/(λ) + \gamma ⋅ f ^{*} \left( (x ^{*} - \beta)/(λ \gamma) \right).

Behavior under linear transformations

Let

A : X \to Y be a bounded linear operator. For any convex function f on X, \left(A f\right) ^{*} = f ^{*} A ^{*}

where

(A f)(y) = inf \{ f(x) : x \in X , A x = y \}

is the preimage of

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

A closed convex function

f is symmetric with respect to a given set G of orthogonal linear transformations,f(A x) = f(x) for all x and all A \in G

if and only if its convex conjugate

f ^{*} is symmetric with respect to G.

Table of selected convex conjugates

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

g(x)	\operatorname{dom}(g)	g ^{*(x} ^{*)}	\operatorname{dom}(g ^{*)}
f(ax) (where a ≠ 0 )	X	f ^{*\left( (x ^{*})/(a)} \right)	X ^{*}
f(x + b)	X	f ^{*(x} ^{*)} - \langle b,x ^{*} \rangle	X ^{*}
a f(x) (where a > 0 )	X	a f ^{*\left( (x ^{*})/(a)} \right)	X ^{*}
\alpha + \beta x + \gamma ⋅ f( λ x + \delta)	X	- \alpha - \delta (x ^{*-\beta})/(λ+) \gamma ⋅ f ^{*} \left( (x ^{*-\beta})/(\gamma λ) \right) (\gamma> 0 )	X ^{*}
(|x| ^{p})/(p) (where p > 1 )	R	(|x ^{*|} ^{q})/(q) (where (1)/(p) + (1)/(q) = 1 )	R
(- x ^{p})/(p) (where 0 < p < 1 )	R _{+}	(- ( - x ^{*)} ^{q})/(q) (where (1)/(p) + (1)/(q) = 1 )	R _{--}
\sqrt{ 1 + x ^{2}}	R	- \sqrt{ 1 - (x ^{*)} ^{2}}	[ -1 , 1 ]
-log (x)	R _{++}	- ( 1 + log ( - x ^{*))}	R _{--}
e ^{x}	R	\begin{cases}x ^{*} log (x ^{*)} - x ^{*} & if x ^{*} > 0 \ 0 & if x ^{*} = 0 \end{cases}	R _{+}
log \left( 1 + e ^{x\right)}	R	\begin{cases}x ^{*} log (x ^{*)} + ( 1 - x ^{*)} log ( 1 - x ^{*)} & if 0 < x ^{*} < 1 \ 0 & if x ^{*} = 0 , 1 \end{cases}	[ 0 , 1 ]
-log \left( 1 - e ^{x\right)}	R _{--}	\begin{cases}x ^{*} log (x ^{*)} - ( 1 + x ^{*)} log ( 1 + x ^{*)} & if x ^{*} > 0 \ 0 & if x ^{*} = 0 \end{cases}	R _{+}

See also

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

References

1. Web site: Legendre Transform . April 14, 2019.
2. Book: Phelps, Robert . Robert R. Phelps

   . Robert R. Phelps . Convex Functions, Monotone Operators and Differentiability. limited . 2 . 1993. Springer . 0-387-56715-1. 42.

3. 10.1137/070687542 . The Proximal Average: Basic Theory . 2008 . Bauschke . Heinz H. . Goebel . Rafal . Lucet . Yves . Wang . Xianfu . SIAM Journal on Optimization . 19 . 2 . 766. 10.1.1.546.4270 .
4. Ioffe, A.D. and Tichomirov, V.M. (1979), Theorie der Extremalaufgaben. Deutscher Verlag der Wissenschaften. Satz 3.4.3
5. Book: Borwein . Jonathan . Jonathan Borwein. Lewis . Adrian . Convex Analysis and Nonlinear Optimization: Theory and Examples. limited . 2 . 2006 . Springer . 978-0-387-29570-1. 50–51.

• Book: Arnol'd , Vladimir Igorevich . Vladimir Igorevich Arnol'd

. Vladimir Igorevich Arnol'd . Mathematical Methods of Classical Mechanics . Second . Springer . 1989 . 0-387-96890-3 . 997295 . registration .

• • Book: Rockafellar , R. Tyrell . R. Tyrrell Rockafellar

. R. Tyrrell Rockafellar . Convex Analysis . Princeton University Press . 1970 . Princeton . 0-691-01586-4 . 0274683.

Further reading

• Web site: Legendre-Fenchel transforms in a nutshell. Touchette. Hugo. 2014-10-16. 2017-01-09. https://web.archive.org/web/20170407134235/http://www.physics.sun.ac.za/~htouchette/archive/notes/lfth2.pdf. 2017-04-07. dead.
• Web site: Elements of convex analysis. 2008-03-26. Touchette. Hugo. 2006-11-21. https://web.archive.org/web/20150526090548/http://www.physics.sun.ac.za/~htouchette/archive/convex1.pdf. 2015-05-26. dead.
• Web site: Legendre and Legendre-Fenchel transforms in a step-by-step explanation. 2013-05-18.
• Book: Intellectual Trespassing as a Way of Life: Essays in Philosophy, Economics, and Mathematics . Chapter 12: Parallel Addition, Series-Parallel Duality, and Financial Mathematics . Series G - Reference, Information and Interdisciplinary Subjects Series . The worldly philosophy: studies in intersection of philosophy and economics . David Patterson . Ellerman . David Patterson Ellerman . . 1995-03-21 . 0-8476-7932-2 . 237–268 . https://books.google.com/books?id=NgJqXXk7zAAC&pg=PA237 . 2019-08-09 . live . https://web.archive.org/web/20160305012729/http://www.ellerman.org/wp-content/uploads/2012/12/IntellectualTrespassingBook.pdf . 2016-03-05. https://web.archive.org/web/20150917191423/http://www.ellerman.org/Davids-Stuff/Maths/sp_math.doc (271 pages)
• Web site: Introduction to Series-Parallel Duality . David Patterson . Ellerman . David Patterson Ellerman . . May 2004 . 1995-03-21 . 10.1.1.90.3666 . 2019-08-09 . live . https://web.archive.org/web/20190810011716/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.3666&rep=rep1&type=pdf . 2019-08-10. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.3666&amp;rep=rep1&amp;type=pdf (24 pages)