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. The convex conjugate is widely used for constructing the dual problem in optimization theory, thus generalizing 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 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
Let F denote a cumulative distribution function of a random variable X. Then,
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 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 is also the closed convex hull, i.e. the largest lower semi-continuous convex function with
For proper functions

Fenchel's inequality

For any function and its convex conjugate, Fenchel's inequality holds for every and
Furthermore, the equality holds only when, where is the subgradient.
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 of two functions and is defined as
The operation is symmetric and associative, i.e.
Let be proper, convex and lower semicontinuous functions on Then the infimal convolution is convex and lower semicontinuous, and satisfies
or, equivalently,
which expresses the behaviour of convex conjugation with respect to sums of functions.
The infimal convolution of two functions has a geometric interpretation: The epigraph of the infimal convolution of two functions is the Minkowski sum of the 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:
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,
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.