HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
, 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 Adrien-Marie Legendre (; ; 18 September 1752 – 9 January 1833) was a French mathematician who made numerous contributions to mathematics. Well-known and important concepts such as the Legendre polynomials and Legendre transformation are name ...
and
Werner Fenchel Moritz Werner Fenchel (; 3 May 1905 – 24 January 1988) was a mathematician known for his contributions to geometry and to optimization theory. Fenchel established the basic results of convex analysis and nonlinear optimization theor ...
). It allows in particular for a far reaching generalization of Lagrangian duality.


Definition

Let X be a real
topological vector space In mathematics, a topological vector space (also called a linear topological space and commonly abbreviated TVS or t.v.s.) is one of the basic structures investigated in functional analysis. A topological vector space is a vector space that is als ...
and let X^ be the
dual space In mathematics, any vector space ''V'' has a corresponding dual vector space (or just dual space for short) consisting of all linear forms on ''V'', together with the vector space structure of pointwise addition and scalar multiplication by cons ...
to X. Denote by :\langle \cdot , \cdot \rangle : X^ \times X \to \mathbb the canonical dual pairing, which is defined by \left( x^*, x \right) \mapsto x^* (x). For a function f : X \to \mathbb \cup \ taking values on the
extended real number line In mathematics, the affinely extended real number system is obtained from the real number system \R by adding two infinity elements: +\infty and -\infty, where the infinities are treated as actual numbers. It is useful in describing the algebra on ...
, its is the function :f^ : X^ \to \mathbb \cup \ whose value at x^* \in X^ is defined to be the
supremum In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest ...
: :f^ \left( x^ \right) := \sup \left\, or, equivalently, in terms of the
infimum In mathematics, the infimum (abbreviated inf; plural infima) of a subset S of a partially ordered set P is a greatest element in P that is less than or equal to each element of S, if such an element exists. Consequently, the term ''greatest lo ...
: :f^ \left( x^ \right) := - \inf \left\. This definition can be interpreted as an encoding of the
convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...
of the function's epigraph in terms of its supporting hyperplanes.


Examples

For more examples, see . * The convex conjugate of an
affine function In Euclidean geometry, an affine transformation or affinity (from the Latin, ''affinis'', "connected with") is a geometric transformation that preserves lines and parallelism, but not necessarily Euclidean distances and angles. More generall ...
f(x) = \left\langle a, x \right\rangle - b is f^\left(x^ \right) = \begin b, & x^ = a \\ +\infty, & x^ \ne a. \end * The convex conjugate of a power function f(x) = \frac, x, ^p, 1 < p < \infty is f^\left(x^ \right) = \frac, x^, ^q, 1 * The convex conjugate of the
absolute value In mathematics, the absolute value or modulus of a real number x, is the non-negative value without regard to its sign. Namely, , x, =x if is a positive number, and , x, =-x if x is negative (in which case negating x makes -x positive), ...
function f(x) = \left, x \ is f^\left(x^ \right) = \begin 0, & \left, x^ \ \le 1 \\ \infty, & \left, x^ \ > 1. \end * The convex conjugate of the
exponential function The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, ...
f(x)= e^x is f^\left(x^ \right) = \begin x^ \ln x^ - x^ , & x^ > 0 \\ 0 , & x^ = 0 \\ \infty , & x^ < 0. \end The convex conjugate and Legendre transform of the exponential function agree except that the
domain Domain may refer to: Mathematics *Domain of a function, the set of input values for which the (total) function is defined ** Domain of definition of a partial function ** Natural domain of a partial function **Domain of holomorphy of a function * ...
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)

Se
this article for example.
Let ''F'' denote a
cumulative distribution function In probability theory and statistics, the cumulative distribution function (CDF) of a real-valued random variable X, or just distribution function of X, evaluated at x, is the probability that X will take a value less than or equal to x. Eve ...
of a
random variable A random variable (also called random quantity, aleatory variable, or stochastic variable) is a mathematical formalization of a quantity or object which depends on random events. It is a mapping or a function from possible outcomes (e.g., the po ...
 ''X''. Then (integrating by parts), f(x):= \int_^x F(u) \, du = \operatorname\left max(0,x-X)\right= x-\operatorname \left min(x,X)\right/math> has the convex conjugate f^(p)= \int_0^p F^(q) \, dq = (p-1)F^(p)+\operatorname\left min(F^(p),X)\right = p F^(p)-\operatorname\left max(0,F^(p)-X)\right


Ordering

A particular interpretation has the transform f^\text(x):= \arg \sup_t t\cdot x-\int_0^1 \max\ \, du, as this is a nondecreasing rearrangement of the initial function ''f''; in particular, f^\text= f 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 (a convex function with polyhedral epigraph) is again a polyhedral convex function.


Order reversing

Declare that f \le g if and only if f(x) \le g(x) for all x. Then convex-conjugation is order-reversing, which by definition means that if f \le g then f^* \ge g^*. For a family of functions \left(f_\alpha\right)_\alpha it follows from the fact that supremums may be interchanged that :\left(\inf_\alpha f_\alpha\right)^*(x^*) = \sup_\alpha f_\alpha^*(x^*), and from the
max–min inequality In mathematics, the max–min inequality is as follows: :For any function \ f : Z \times W \to \mathbb\ , :: \sup_ \inf_ f(z, w) \leq \inf_ \sup_ f(z, w)\ . When equality holds one says that , , and satisfies a strong max–min property (or a s ...
that :\left(\sup_\alpha f_\alpha\right)^*(x^*) \le \inf_\alpha f_\alpha^*(x^*).


Biconjugate

The convex conjugate of a function is always
lower semi-continuous In mathematical analysis, semicontinuity (or semi-continuity) is a property of extended real-valued functions that is weaker than continuity. An extended real-valued function f is upper (respectively, lower) semicontinuous at a point x_0 if, ro ...
. The biconjugate f^ (the convex conjugate of the convex conjugate) is also the closed convex hull, i.e. the largest
lower semi-continuous In mathematical analysis, semicontinuity (or semi-continuity) is a property of extended real-valued functions that is weaker than continuity. An extended real-valued function f is upper (respectively, lower) semicontinuous at a point x_0 if, ro ...
convex function with f^ \le f. For proper functions f, :f = f^
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (shortened as "iff") is a biconditional logical connective between statements, where either both statements are true or both are false. The connective is bic ...
f is convex and lower semi-continuous, by the
Fenchel–Moreau theorem In convex analysis, the Fenchel–Moreau theorem (named after Werner Fenchel and Jean Jacques Moreau) or Fenchel biconjugation theorem (or just biconjugation theorem) is a theorem which gives necessary and sufficient conditions for a function t ...
.


Fenchel's inequality

For any function and its convex conjugate , Fenchel's inequality (also known as the Fenchel–Young inequality) holds for every x \in X and :\left\langle p,x \right\rangle \le f(x) + f^*(p). The proof follows from the definition of convex conjugate: f^*(p) = \sup_ \left\ \ge \langle p,x \rangle - f(x).


Convexity

For two functions f_0 and f_1 and a number 0 \le \lambda \le 1 the convexity relation :\left((1-\lambda) f_0 + \lambda f_1\right)^ \le (1-\lambda) f_0^ + \lambda f_1^ holds. The operation is a convex mapping itself.


Infimal convolution

The infimal convolution (or epi-sum) of two functions f and g is defined as :\left( f \operatorname g \right)(x) = \inf \left\. Let f_1, \ldots, f_ be proper, convex and lower semicontinuous functions on \mathbb^. Then the infimal convolution is convex and lower semicontinuous (but not necessarily proper), and satisfies :\left( f_1 \operatorname \cdots \operatorname f_m \right)^ = f_1^ + \cdots + f_m^. 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 f is differentiable, then its derivative is the maximizing argument in the computation of the convex conjugate: :f^\prime(x) = x^*(x):= \arg\sup_ -f^\left( x^ \right) and :f^\left( x^ \right) = x\left( x^ \right):= \arg\sup_x - f(x); whence :x = \nabla f^\left( \nabla f(x) \right), :x^ = \nabla f\left( \nabla f^\left( x^ \right)\right), and moreover :f^(x) \cdot f^\left( x^(x) \right) = 1, :f^\left( x^ \right) \cdot f^\left( x(x^) \right) = 1.


Scaling properties

If for some \gamma>0, g(x) = \alpha + \beta x + \gamma \cdot f\left( \lambda x + \delta \right), then :g^\left( x^ \right)= - \alpha - \delta\frac \lambda + \gamma \cdot f^\left(\frac \right).


Behavior under linear transformations

Let A : X \to Y be a
bounded linear operator In functional analysis and operator theory, a bounded linear operator is a linear transformation L : X \to Y between topological vector spaces (TVSs) X and Y that maps bounded subsets of X to bounded subsets of Y. If X and Y are normed vect ...
. For any convex function f on X, :\left(A f\right)^ = f^ A^ where :(A f)(y) = \inf\ is the preimage of f with respect to 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, :f(A x) = f(x) for all x and all A \in G 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.


See also

*
Dual problem In mathematical optimization theory, duality or the duality principle is the principle that optimization problems may be viewed from either of two perspectives, the primal problem or the dual problem. If the primal is a minimization problem then ...
* Fenchel's duality theorem * Legendre transformation *
Young's inequality for products In mathematics, Young's inequality for products is a mathematical inequality about the product of two numbers. The inequality is named after William Henry Young and should not be confused with Young's convolution inequality. Young's inequality f ...


References

* * *


Further reading

* * * *

(271 pages) *

(24 pages) {{Convex analysis and variational analysis Convex analysis Duality theories Theorems involving convexity Transforms