Generalization of the Legendre transformation
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
be a real topological vector space and let
be the dual space to
. Denote by
![{\displaystyle \langle \cdot ,\cdot \rangle :X^{*}\times X\to \mathbb {R} }](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
the canonical dual pairing, which is defined by
For a function
taking values on the extended real number line, its convex conjugate is the function
![{\displaystyle f^{*}:X^{*}\to \mathbb {R} \cup \{-\infty ,+\infty \}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
whose value at
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\},}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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 § Table of selected convex conjugates.
- The convex conjugate of an affine function
is ![{\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}b,&x^{*}=a\\+\infty ,&x^{*}\neq a.\end{cases}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- The convex conjugate of a power function
is ![{\displaystyle f^{*}\left(x^{*}\right)={\frac {1}{q}}|x^{*}|^{q},1<q<\infty ,{\text{where}}{\tfrac {1}{p}}+{\tfrac {1}{q}}=1.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- The convex conjugate of the absolute value function
is ![{\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}0,&\left|x^{*}\right|\leq 1\\\infty ,&\left|x^{*}\right|>1.\end{cases}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
- The convex conjugate of the exponential function
is ![{\displaystyle f^{*}\left(x^{*}\right)={\begin{cases}x^{*}\ln x^{*}-x^{*},&x^{*}>0\\0,&x^{*}=0\\\infty ,&x^{*}<0.\end{cases}}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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),
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].}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Ordering
A particular interpretation has the transform
as this is a nondecreasing rearrangement of the initial function f; in particular,
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
if and only if
for all
Then convex-conjugation is order-reversing, which by definition means that if
then
For a family of functions
it follows from the fact that supremums may be interchanged that
![{\displaystyle \left(\inf _{\alpha }f_{\alpha }\right)^{*}(x^{*})=\sup _{\alpha }f_{\alpha }^{*}(x^{*}),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
and from the max–min inequality that
![{\displaystyle \left(\sup _{\alpha }f_{\alpha }\right)^{*}(x^{*})\leq \inf _{\alpha }f_{\alpha }^{*}(x^{*}).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Biconjugate
The convex conjugate of a function is always lower semi-continuous. The biconjugate
(the convex conjugate of the convex conjugate) is also the closed convex hull, i.e. the largest lower semi-continuous convex function with
For proper functions
if and only if
is convex and lower semi-continuous, by the Fenchel–Moreau theorem.
Fenchel's inequality
For any function f and its convex conjugate f *, Fenchel's inequality (also known as the Fenchel–Young inequality) holds for every
and
:
![{\displaystyle \left\langle p,x\right\rangle \leq f(x)+f^{*}(p).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Furthermore, the equality holds only when
.
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).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Convexity
For two functions
and
and a number
the convexity relation
![{\displaystyle \left((1-\lambda )f_{0}+\lambda f_{1}\right)^{*}\leq (1-\lambda )f_{0}^{*}+\lambda f_{1}^{*}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
holds. The
operation is a convex mapping itself.
Infimal convolution
The infimal convolution (or epi-sum) of two functions
and
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\}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Let
be proper, convex and lower semicontinuous functions on
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}^{*}.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
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
is differentiable, then its derivative is the maximizing argument in the computation of the convex conjugate:
and![{\displaystyle f^{{*}\prime }\left(x^{*}\right)=x\left(x^{*}\right):=\arg \sup _{x}{\langle x,x^{*}\rangle }-f(x);}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
hence
![{\displaystyle x=\nabla f^{*}\left(\nabla f(x)\right),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle x^{*}=\nabla f\left(\nabla f^{*}\left(x^{*}\right)\right),}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
and moreover
![{\displaystyle f^{\prime \prime }(x)\cdot f^{{*}\prime \prime }\left(x^{*}(x)\right)=1,}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
![{\displaystyle f^{{*}\prime \prime }\left(x^{*}\right)\cdot f^{\prime \prime }\left(x(x^{*})\right)=1.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Scaling properties
If for some
, then
![{\displaystyle g^{*}\left(x^{*}\right)=-\alpha -\delta {\frac {x^{*}-\beta }{\lambda }}+\gamma \cdot f^{*}\left({\frac {x^{*}-\beta }{\lambda \gamma }}\right).}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Behavior under linear transformations
Let
be a bounded linear operator. For any convex function
on
![{\displaystyle \left(Af\right)^{*}=f^{*}A^{*}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
where
![{\displaystyle (Af)(y)=\inf\{f(x):x\in X,Ax=y\}}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
is the preimage of
with respect to
and
is the adjoint operator of
[4]
A closed convex function
is symmetric with respect to a given set
of orthogonal linear transformations,
for all
and all ![{\displaystyle A\in G}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
if and only if its convex conjugate
is symmetric with respect to ![{\displaystyle G.}](data:image/gif;base64,R0lGODlhAQABAIAAAAAAAP///yH5BAEAAAAALAAAAAABAAEAAAIBRAA7)
Table of selected convex conjugates
The following table provides Legendre transforms for many common functions as well as a few useful properties.[5]
See also
References
- ^ "Legendre Transform". Retrieved April 14, 2019.
- ^ Phelps, Robert (1993). Convex Functions, Monotone Operators and Differentiability (2 ed.). Springer. p. 42. ISBN 0-387-56715-1.
- ^ Bauschke, Heinz H.; Goebel, Rafal; Lucet, Yves; Wang, Xianfu (2008). "The Proximal Average: Basic Theory". SIAM Journal on Optimization. 19 (2): 766. CiteSeerX 10.1.1.546.4270. doi:10.1137/070687542.
- ^ Ioffe, A.D. and Tichomirov, V.M. (1979), Theorie der Extremalaufgaben. Deutscher Verlag der Wissenschaften. Satz 3.4.3
- ^ Borwein, Jonathan; Lewis, Adrian (2006). Convex Analysis and Nonlinear Optimization: Theory and Examples (2 ed.). Springer. pp. 50–51. ISBN 978-0-387-29570-1.
Further reading
- 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.
- "Legendre and Legendre-Fenchel transforms in a step-by-step explanation". Retrieved 2013-05-18.
- 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)