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 formula_1 be a real topological vector space and let formula_2 be the dual space to formula_1. Denote by 
the canonical dual pairing, which is defined by formula_5 
For a function formula_6 taking values on the extended real number line, its is the function
whose value at formula_8 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 .
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, formula_21 for "ƒ" 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 formula_22 if and only if formula_23 for all formula_24 Then convex-conjugation is order-reversing, which by definition means that if formula_22 then formula_26 
For a family of functions formula_27 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 formula_30 (the convex conjugate of the convex conjugate) is also the closed convex hull, i.e. the largest lower semi-continuous convex function with formula_31 
For proper functions formula_32 
Fenchel's inequality.
For any function and its convex conjugate , Fenchel's inequality (also known as the Fenchel–Young inequality) holds for every formula_35 and 
The proof follows from the definition of convex conjugate: formula_37
Convexity.
For two functions formula_38 and formula_39 and a number formula_40 the convexity relation 
holds. The formula_42 operation is a convex mapping itself.
Infimal convolution.
The infimal convolution (or epi-sum) of two functions formula_34 and formula_44 is defined as
Let formula_46 be proper, convex and lower semicontinuous functions on formula_47 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 formula_34 is differentiable, then its derivative is the maximizing argument in the computation of the convex conjugate: