Open main menu

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 or Fenchel transformation (after Adrien-Marie Legendre and Werner Fenchel). It allows in particular for a far reaching generalization of Lagrangian duality.

DefinitionEdit

Let   be a real topological vector space, and let   be the dual space to  . Denote the dual pairing by

 

For a function

 

taking values on the extended real number line, the convex conjugate

 

is defined in terms of the supremum by

 

or, equivalently, in terms of the infimum by

 

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

ExamplesEdit

The convex conjugate of an affine function

 

is

 

The convex conjugate of a power function

 

is

 

where  

The convex conjugate of the absolute value function

 

is

 

The convex conjugate of the exponential function   is

 

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

Let F denote a cumulative distribution function of a random variable X. Then (integrating by parts),

 

has the convex conjugate

 

OrderingEdit

A particular interpretation has the transform

 

as this is a nondecreasing rearrangement of the initial function f; in particular,   for ƒ nondecreasing.

PropertiesEdit

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 reversingEdit

Convex-conjugation is order-reversing: if   then  . Here

 

For a family of functions   it follows from the fact that supremums may be interchanged that

 

and from the max–min inequality that

 

BiconjugateEdit

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 f,

  if and only if f is convex and lower semi-continuous by Fenchel–Moreau theorem.

Fenchel's inequalityEdit

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

 

The proof follows immediately from the definition of convex conjugate:  .


ConvexityEdit

For two functions   and   and a number   the convexity relation

 

holds. The   operation is a convex mapping itself.

Infimal convolutionEdit

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

 

Let f1, …, fm be proper, convex and lower semicontinuous functions on Rn. Then the infimal convolution is convex and lower semicontinuous (but not necessarily proper),[3] 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.[4]

Maximizing argumentEdit

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

  and
 

whence

 
 

and moreover

 
 

Scaling propertiesEdit

If, for some  ,  , then

 

In case of an additional parameter (α, say) moreover[clarification needed]

 

where   is chosen to be the maximizing argument.

Behavior under linear transformationsEdit

Let A be a bounded linear operator from X to Y. For any convex function f on X, one has

 

where

 

is the preimage of f w.r.t. A and A* is the adjoint operator of A.[5]

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

 

if and only if its convex conjugate f* is symmetric with respect to G.

Table of selected convex conjugatesEdit

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

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

See alsoEdit

ReferencesEdit

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

External linksEdit