The Legendre transform is an self-inverse transformation on real-valued convex functions of one real variable. The generalization of the Legendre transformation to affine spaces and non-convex functions is known as the convex conjugate (also called the Legendre–Fenchel transformation), which can be used to construct a function’s convex hull.
Definition
Let $f$ be a convex function. The Legendre transform of $f$ is defined as
$$f^*(y)=\sup_x y^T x-f(x),$$
which is always well-defined when $f(x)$ is convex. If $f$ is differentiable, the optimal is achieved when $x=(f’)^{-1}(y)$.
Perperties
The Legendre transform of a convex function is convex.
It follows that the Legendre transformation is an involution, i.e., $f=f^{**}$.
For a differentiable convex function $f$ and suppose that $f’$ is invertible, then $(f^*)’=(f’)^{-1}$.
Scaling properties: for any $a>0$,
- $f(x)=ag(x)\Rightarrow f^{*}(p)=ag^{*}(\frac{p}a)$.
- $f(x)=g(ax)\Rightarrow f^{*}(p)=g^{*}(\frac{p}a)$.
Fenchel–Young inequality
For any function $f$ and its convex conjugate $f^{*}$ Fenchel’s inequality (also known as the Fenchel–Young inequality) holds for every $x \in X$ and $p \in X^{*}$, i.e., independent $x, p$ pairs, $$\langle p, x\rangle \leq f(x)+f^{*}(p).$$
- Infimal convolution theorem
For any convex $f_i$, if $$g(x)=\inf \{f_1\left(x_1\right)+f_2\left(x_2\right) \mid x_1+x_2=x\}$$ then $$g^*(y)=f_1^{*}(y)+f_2^{*}(y).$$
Let $f,g$ be proper convex functions on $\mathcal{X}$. If $\operatorname{dom}f\cap\operatorname{g}$ contains a point at which $f$ or $g$ is continuous, then $$(f+g)^{*}=f^{*}\square g^{*}.$$ Proof. See R. T . Rockafellar’s paper: Extension of Fenchel’s duality theorem. or Theorem 3.4 in Thomas Stromberg’s thesis: A Study of the Operation of Infimal Convolution.
Example: Affine function
Consider $f(x)=a^Tx+b$. The convex conjugate is $$f^*(y)=\sup_x y^Tx-ax-b.$$
This function is bounded iff $y-a=0$. I.e.,
$$f^*(y)=\left\{\begin{array}{l} -b, \text{ if } y=a; \\ +\infty, \text{ otherwise.} \end{array}\right.$$
References
[1] 走近中神通Fenchel