Legendre Transformation and Fenchel Conjugate
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