Editing Convex conjugate

{{Short description|Generalization of the Legendre transformation}}
<!-- Contents mostly taken from [[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]]).  The convex conjugate is widely used for constructing the [[Duality (optimization)|dual problem]] in [[optimization theory]], thus generalizing [[Duality (optimization)#Lagrange duality|Lagrangian duality]].

== Definition ==

Let <math>X</math> be a [[real number|real]] [[topological vector space]] and let <math>X^{*}</math> be the [[dual space]] to <math>X</math>. Denote by 

:<math>\langle \cdot , \cdot \rangle : X^{*} \times X \to \mathbb{R}</math>

the canonical [[dual pair]]ing, which is defined by <math>\left\langle x^*, x \right\rangle \mapsto x^* (x).</math> 

For a function <math>f : X \to \mathbb{R} \cup \{ - \infty, + \infty \}</math> taking values on the [[extended real number line]], its '''{{em|convex conjugate}}''' is the function

:<math>f^{*} : X^{*} \to \mathbb{R} \cup \{ - \infty, + \infty \}</math>

whose value at <math>x^* \in X^{*}</math> is defined to be the [[supremum]]:

:<math>f^{*} \left( x^{*} \right) := \sup \left\{ \left\langle x^{*}, x \right\rangle - f (x) ~\colon~ x \in X \right\},</math>

or, equivalently, in terms of the [[infimum]]:

:<math>f^{*} \left( x^{*} \right) := - \inf \left\{ f (x) - \left\langle x^{*}, x \right\rangle ~\colon~ x \in X \right\}.</math>

This definition can be interpreted as an encoding of the [[convex hull]] of the function's [[Epigraph (mathematics)|epigraph]] in terms of its [[supporting hyperplane]]s.<ref>{{cite web|url=https://physics.stackexchange.com/a/9360/821 |title=Legendre Transform |accessdate=April 14, 2019}}</ref>

== Examples ==
For more examples, see {{Section link||Table of selected convex conjugates}}.
* The convex conjugate of an [[affine function]] <math> f(x) = \left\langle a, x \right\rangle - b</math> is <math display="block"> f^{*}\left(x^{*} \right)
= \begin{cases} b,      & x^{*}   =  a
             \\ +\infty, & x^{*}  \ne a.
  \end{cases}
</math>
* The convex conjugate of a [[power function]] <math> f(x) = \frac{1}{p}|x|^p, 1 < p < \infty </math> is <math display="block">
f^{*}\left(x^{*} \right) = \frac{1}{q}|x^{*}|^q, 1<q<\infty, \text{where} \tfrac{1}{p} + \tfrac{1}{q} = 1.</math>
* The convex conjugate of the [[absolute value]] function <math>f(x) = \left| x \right|</math> is <math display="block">
f^{*}\left(x^{*} \right)
= \begin{cases} 0,      & \left|x^{*} \right| \le 1
             \\ \infty, & \left|x^{*} \right|  >  1.
  \end{cases}
</math>
* The convex conjugate of the [[exponential function]] <math>f(x)= e^x</math> is <math display="block">
f^{*}\left(x^{*} \right)
= \begin{cases} x^{*} \ln x^{*} - x^{*}      , & x^{*}  > 0
             \\ 0                            , & x^{*}  = 0
             \\ \infty                       , & x^{*}  < 0.
  \end{cases}
</math>

The convex conjugate and Legendre transform of the exponential function agree except that the [[domain of a function|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 [https://link.springer.com/article/10.1007/s10107-014-0801-1 this article for example.]

Let ''F'' denote a [[cumulative distribution function]] of a [[random variable]]&nbsp;''X''. Then ([[Integration by parts|integrating by parts]]),
<math display="block">f(x):= \int_{-\infty}^x F(u) \, du = \operatorname{E}\left[\max(0,x-X)\right] = x-\operatorname{E} \left[\min(x,X)\right]</math>
has the convex conjugate
<math display="block">f^{*}(p)= \int_0^p F^{-1}(q) \, dq = (p-1)F^{-1}(p)+\operatorname{E}\left[\min(F^{-1}(p),X)\right] 
 = p F^{-1}(p)-\operatorname{E}\left[\max(0,F^{-1}(p)-X)\right].</math>

=== Ordering ===
A particular interpretation has the transform
<math display="block">f^\text{inc}(x):= \arg \sup_t t\cdot x-\int_0^1 \max\{t-f(u),0\} \, du,</math>
as this is a nondecreasing rearrangement of the initial function ''f''; in particular, <math>f^\text{inc}= f</math> 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 [[Polyhedron|polyhedral]] [[Epigraph (mathematics)|epigraph]]) is again a polyhedral convex function.

=== Order reversing===

Declare that <math>f \le g</math> if and only if <math>f(x) \le g(x)</math> for all <math>x.</math> Then convex-conjugation is [[Order theory|order-reversing]], which by definition means that if <math>f \le g</math> then <math>f^* \ge g^*.</math> 

For a family of functions <math>\left(f_\alpha\right)_\alpha</math> it follows from the fact that supremums may be interchanged that

:<math>\left(\inf_\alpha f_\alpha\right)^*(x^*) = \sup_\alpha f_\alpha^*(x^*),</math>

and from the [[max–min inequality]] that 

:<math>\left(\sup_\alpha f_\alpha\right)^*(x^*) \le \inf_\alpha f_\alpha^*(x^*).</math>

=== Biconjugate ===
The convex conjugate of a function is always [[lower semi-continuous]]. The '''biconjugate''' <math>f^{**}</math> (the convex conjugate of the convex conjugate) is also the [[closed convex hull]], i.e. the largest [[lower semi-continuous]] convex function with <math>f^{**} \le f.</math> 
For [[Proper convex function|proper functions]] <math>f,</math> 

:<math>f = f^{**}</math> [[if and only if]] <math>f</math> is convex and lower semi-continuous, by the [[Fenchel–Moreau theorem]].

=== Fenchel's inequality ===
For any function {{mvar|f}}  and its convex conjugate {{math|''f'' *}}, '''Fenchel's inequality''' (also known as the '''Fenchel–Young inequality''') holds for every <math>x \in X</math>  and {{nowrap|<math>p \in X^{*}</math>:}}

:<math>\left\langle p,x \right\rangle \le f(x) + f^*(p).</math>

Furthermore, the equality holds only when <math>p \in \partial f(x)</math>.
The proof follows from the definition of convex conjugate: <math>f^*(p) = \sup_{\tilde x} \left\{ \langle p,\tilde x \rangle - f(\tilde x) \right\} \ge \langle p,x \rangle - f(x).</math>

=== Convexity ===
For two functions <math>f_0</math> and <math>f_1</math> and a number <math>0 \le \lambda \le 1</math> the convexity relation 

:<math>\left((1-\lambda) f_0 + \lambda f_1\right)^{*} \le (1-\lambda) f_0^{*} + \lambda f_1^{*}</math>

holds. The <math>{*}</math> operation is a convex mapping itself.

=== Infimal convolution ===
The '''infimal convolution''' (or epi-sum) of two functions <math>f</math> and <math>g</math> is defined as

:<math>\left( f \operatorname{\Box} g \right)(x) = \inf \left\{ f(x-y) + g(y) \mid y \in \mathbb{R}^n \right\}.</math>

Let <math>f_1, \ldots, f_{m}</math> be [[Proper convex function|proper]], convex and [[Semi-continuity|lower semicontinuous]] functions on <math>\mathbb{R}^{n}.</math> Then the infimal convolution is convex and lower semicontinuous (but not necessarily proper),<ref>{{cite book |last=Phelps |first=Robert |authorlink=Robert R. Phelps |title=Convex Functions, Monotone Operators and Differentiability|url=https://archive.org/details/convexfunctionsm00phel |url-access=limited | edition=2 |year=1993|publisher=Springer |isbn= 0-387-56715-1|page= [https://archive.org/details/convexfunctionsm00phel/page/n50 42]}}</ref> and satisfies

:<math>\left( f_1 \operatorname{\Box} \cdots \operatorname{\Box} f_m \right)^{*} = f_1^{*} + \cdots + f_m^{*}.</math>

The infimal convolution of two functions has a geometric interpretation:  The (strict) [[epigraph (mathematics)|epigraph]] of the infimal convolution of two functions is the [[Minkowski sum]] of the (strict) epigraphs of those functions.<ref>{{cite journal |doi=10.1137/070687542 |title=The Proximal Average: Basic Theory |year=2008 |last1=Bauschke |first1=Heinz H. |last2=Goebel |first2=Rafal |last3=Lucet |first3=Yves |last4=Wang |first4=Xianfu |journal=SIAM Journal on Optimization |volume=19 |issue=2 |pages=766|citeseerx=10.1.1.546.4270 }}</ref>

=== Maximizing argument ===
If the function <math>f</math> is differentiable, then its derivative is the maximizing argument in the computation of the convex conjugate:
:<math>f^\prime(x) = x^*(x):= \arg\sup_{x^{*}} {\langle x, x^{*}\rangle} -f^{*}\left( x^{*} \right)</math> and
:<math>f^{{*}\prime}\left( x^{*} \right) = x\left( x^{*} \right):= \arg\sup_x {\langle x, x^{*}\rangle} - f(x);</math>

hence
:<math>x = \nabla f^{{*}}\left( \nabla f(x) \right),</math>
:<math>x^{*} = \nabla f\left( \nabla f^{{*}}\left( x^{*} \right)\right),</math>

and moreover
:<math>f^{\prime\prime}(x) \cdot f^{{*}\prime\prime}\left( x^{*}(x) \right) = 1,</math>
:<math>f^{{*}\prime\prime}\left( x^{*} \right) \cdot f^{\prime\prime}\left( x(x^{*}) \right) = 1.</math>

=== Scaling properties ===
If for some <math>\gamma>0,</math> <math>g(x) = \alpha + \beta x + \gamma \cdot f\left( \lambda x + \delta \right)</math>, then 
:<math>g^{*}\left( x^{*} \right)= - \alpha - \delta\frac{x^{*}-\beta} \lambda + \gamma \cdot f^{*}\left(\frac {x^{*}-\beta}{\lambda \gamma}\right).</math>

=== Behavior under linear transformations ===
Let <math>A : X \to Y</math> be a [[bounded linear operator]]. For any convex function <math>f</math> on <math>X,</math> 

:<math>\left(A f\right)^{*} = f^{*} A^{*}</math>

where

:<math>(A f)(y) = \inf\{ f(x) : x \in X , A x = y \}</math>

is the preimage of <math>f</math> with respect to <math>A</math> and <math>A^{*}</math> is the [[adjoint operator]] of <math>A.</math><ref>Ioffe, A.D. and Tichomirov, V.M. (1979), ''Theorie der Extremalaufgaben''. [[Deutscher Verlag der Wissenschaften]]. Satz 3.4.3</ref>

A closed convex function <math>f</math> is symmetric with respect to a given set <math>G</math> of [[orthogonal matrix|orthogonal linear transformation]]s,

:<math>f(A x) = f(x)</math> for all <math>x</math> and all <math>A \in G</math>

if and only if its convex conjugate <math>f^{*}</math> is symmetric with respect to <math>G.</math>

== Table of selected convex conjugates ==
The following table provides Legendre transforms for many common functions as well as a few useful properties.<ref>{{cite book |last1=Borwein |first1=Jonathan |authorlink1=Jonathan Borwein|last2=Lewis |first2=Adrian |title=Convex Analysis and Nonlinear Optimization: Theory and Examples|url=https://archive.org/details/convexanalysisno00borw_812 |url-access=limited | edition=2 |year=2006 |publisher=Springer |isbn=978-0-387-29570-1|pages=[https://archive.org/details/convexanalysisno00borw_812/page/n62 50]–51}}</ref>

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

== See also ==
* [[Dual problem]]
* [[Fenchel's duality theorem]]
* [[Legendre transformation]]
* [[Young's inequality for products]]

== References ==
<references/>
* {{cite book
  | authorlink=Vladimir Igorevich Arnol'd
  | last=Arnol'd
  | first=Vladimir Igorevich
  | title=Mathematical Methods of Classical Mechanics
  | edition=Second
  | publisher=Springer
  | year=1989
  | isbn=0-387-96890-3
  | mr=997295
  | url-access=registration
  | url=https://archive.org/details/mathematicalmeth0000arno
  }}
* {{Rockafellar Wets Variational Analysis 2009 Springer}} <!-- {{sfn|Rockafellar|Wets|2009|p=}} -->
* {{cite book
  | last = Rockafellar
  | first = R. Tyrell
  | authorlink = R. Tyrrell Rockafellar
  | title = Convex Analysis
  | publisher = Princeton University Press
  | year = 1970
  | location = Princeton
  | isbn=0-691-01586-4
  | mr = 0274683
}}

== Further reading ==
* {{cite web
|url = http://www.physics.sun.ac.za/~htouchette/archive/notes/lfth2.pdf
|title = Legendre-Fenchel transforms in a nutshell
|last = Touchette
|first = Hugo
|date = 2014-10-16
|website = 
|publisher = 
|accessdate = 2017-01-09
|archive-url = https://web.archive.org/web/20170407134235/http://www.physics.sun.ac.za/~htouchette/archive/notes/lfth2.pdf
|archive-date = 2017-04-07
|url-status = dead
}}

* {{cite web
|url = http://www.physics.sun.ac.za/~htouchette/archive/convex1.pdf
|title = Elements of convex analysis
|accessdate = 2008-03-26
|last = Touchette
|first = Hugo
|date = 2006-11-21
|archive-url = https://web.archive.org/web/20150526090548/http://www.physics.sun.ac.za/~htouchette/archive/convex1.pdf
|archive-date = 2015-05-26
|url-status = dead
}}

* {{cite book |title=Intellectual Trespassing as a Way of Life: Essays in Philosophy, Economics, and Mathematics |chapter=Chapter 12: Parallel Addition, Series-Parallel Duality, and Financial Mathematics |quote=Series G - Reference, Information and Interdisciplinary Subjects Series |series=The worldly philosophy: studies in intersection of philosophy and economics |author-first=David Patterson |author-last=Ellerman |author-link=David Patterson Ellerman |publisher=[[Rowman & Littlefield Publishers, Inc.]] |date=1995-03-21 |isbn=0-8476-7932-2 |pages=237–268 |url=http://www.ellerman.org/wp-content/uploads/2012/12/IntellectualTrespassingBook.pdf |chapter-url=https://books.google.com/books?id=NgJqXXk7zAAC&pg=PA237 |access-date=2019-08-09 |url-status=live |archive-url=https://web.archive.org/web/20160305012729/http://www.ellerman.org/wp-content/uploads/2012/12/IntellectualTrespassingBook.pdf |archive-date=2016-03-05}} [https://web.archive.org/web/20150917191423/http://www.ellerman.org/Davids-Stuff/Maths/sp_math.doc] (271 pages)

* {{cite web |title=Introduction to Series-Parallel Duality |author-first=David Patterson |author-last=Ellerman |author-link=David Patterson Ellerman |publisher=[[University of California at Riverside]] |date=May 2004 |orig-year=1995-03-21 |citeseerx=10.1.1.90.3666 |url=http://www.ellerman.org/wp-content/uploads/2012/12/Series-Parallel-Duality.CV_.pdf |access-date=2019-08-09 |url-status=live |archive-url=https://web.archive.org/web/20190810011716/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.3666&rep=rep1&type=pdf<!-- https://archive.today/20190810080659/http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.3666&rep=rep1&type=pdf --> |archive-date=2019-08-10}} [http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.90.3666&rep=rep1&type=pdf] (24 pages)

{{Convex analysis and variational analysis}}

[[Category:Convex analysis]]
[[Category:Duality theories]]
[[Category:Theorems involving convexity]]
[[Category:Transforms]]