Convex conjugate

(Redirected from Infimal convolute)

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.

Definition

edit

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 convex conjugate 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.[1]

Examples

edit

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

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

edit

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

edit

A particular interpretation has the transform   as this is a nondecreasing rearrangement of the initial function f; in particular,   for f nondecreasing.

Properties

edit

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

edit

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

edit

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

edit

For any function f and its convex conjugate f *, 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

edit

For two functions   and   and a number   the convexity relation

 

holds. The   operation is a convex mapping itself.

Infimal convolution

edit

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),[2] 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.[3]

Maximizing argument

edit

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

edit

If for some    , then

 

Behavior under linear transformations

edit

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  [4]

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

edit

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

       
  (where  )      
       
  (where  )      
       
  (where  )     (where  )  
  (where  )     (where  )  
       
       
       
       
       

See also

edit

References

edit
  1. ^ "Legendre Transform". Retrieved April 14, 2019.
  2. ^ Phelps, Robert (1993). Convex Functions, Monotone Operators and Differentiability (2 ed.). Springer. p. 42. ISBN 0-387-56715-1.
  3. ^ 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.
  4. ^ Ioffe, A.D. and Tichomirov, V.M. (1979), Theorie der Extremalaufgaben. Deutscher Verlag der Wissenschaften. Satz 3.4.3
  5. ^ 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

edit