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.
be a real topological vector space and let
Denote by the canonical dual pairing, which is defined by
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] For more examples, see § Table of selected convex conjugates.
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.
Let F denote a cumulative distribution function of a random variable X.
as this is a nondecreasing rearrangement of the initial function f; in particular,
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.
Then convex-conjugation is order-reversing, which by definition means that if
it follows from the fact that supremums may be interchanged that and from the max–min inequality that The convex conjugate of a function is always lower semi-continuous.
(the convex conjugate of the convex conjugate) is also the closed convex hull, i.e. the largest lower semi-continuous convex function with
For any function f and its convex conjugate f *, Fenchel's inequality (also known as the Fenchel–Young inequality) holds for every
The proof follows from the definition of convex conjugate:
the convexity relation holds.
operation is a convex mapping itself.
The infimal convolution (or epi-sum) of two functions
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.
is differentiable, then its derivative is the maximizing argument in the computation of the convex conjugate: hence and moreover If for some
g ( x ) = α + β x + γ ⋅ f
be a bounded linear operator.
[4] A closed convex function
is symmetric with respect to a given set
of orthogonal linear transformations, if and only if its convex conjugate
The following table provides Legendre transforms for many common functions as well as a few useful properties.