In mathematics and mathematical optimization, the convex conjugate of a function is a generalization of the Legendre transformation. It is also known as Legendre–Fenchel transformation or Fenchel transformation (after Adrien-Marie Legendre and Werner Fenchel). It is used to transform an optimization problem into its corresponding dual problem, which can often be simpler to solve.
Contents
Definition
Let
For a functional
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.
Examples
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
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)
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,
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
Convex-conjugation is order-reversing: if
For a family of functions
and from the max–min inequality that
Biconjugate
The convex conjugate of a function is always lower semi-continuous. The biconjugate
Fenchel's inequality
For any function f and its convex conjugate f *, Fenchel's inequality (also known as the Fenchel–Young inequality) holds for every x ∈ X and p ∈ X * :
Convexity
For two functions
holds. The
Infimal convolution
The infimal convolution (or epi-sum) of two functions f and g is defined as
Let f1, …, fm be proper, convex and lsc functions on Rn. Then the infimal convolution is convex and lsc (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
whence
and moreover
Scaling properties
If, for some
In case of an additional parameter (α, say) moreover
where
Behavior under linear transformations
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.
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 conjugates
The following table provides Legendre transforms for many common functions as well as a few useful properties.