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).  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 

the canonical dual pairing, which is defined by  

For a function  taking values on the extended real number line, its  is the function

whose value at  is defined to be the supremum:

or, equivalently, in terms of the infimum:

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

Examples 
For more examples, see .
 The convex conjugate of an affine function  is 
 The convex conjugate of a power function  is 
 The convex conjugate of the absolute value function  is 
 The convex conjugate of the exponential function  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),

has the convex conjugate

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

and from the max–min inequality that

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   and its convex conjugate , Fenchel's inequality (also known as the Fenchel–Young inequality) holds for every   and 

Furthermore, the equality holds only when .
The proof follows from the definition of convex conjugate:

Convexity 
For two functions  and  and a number  the convexity relation 

holds. The  operation is a convex mapping itself.

Infimal convolution 
The infimal convolution (or epi-sum) of two functions  and  is defined as

Let  be proper, convex and lower semicontinuous functions on  Then the infimal convolution is convex and lower semicontinuous (but not necessarily proper), and satisfies

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.

Maximizing argument 
If the function  is differentiable, then its derivative is the maximizing argument in the computation of the convex conjugate:
 and

hence

and moreover

Scaling properties 
If for some  , then

Behavior under linear transformations 
Let  be a bounded linear operator. For any convex function  on  

where

is the preimage of  with respect to  and  is the adjoint operator of 

A closed convex function  is symmetric with respect to a given set  of orthogonal linear transformations,

 for all  and all 

if and only if its convex conjugate  is symmetric with respect to

Table of selected convex conjugates 
The following table provides Legendre transforms for many common functions as well as a few useful properties.

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

References

Further reading 
 

 

 

   (271 pages)

   (24 pages)

Convex analysis
Duality theories
Theorems involving convexity
Transforms