Section 1.3: Fenchel Conjugate
Let \(f : \mathbb{R}^d \to \mathbb{R} \cup \{+\infty\}\) be a proper convex function. Its Fenchel conjugate (also called the convex conjugate) is defined as:
\[ f^*(\mathbf{y}) = \sup_{\mathbf{x} \in \text{dom}(f)} \left\{ \mathbf{x}^{\top} \mathbf{y} - f(\mathbf{x}) \right\}, \] where the domain of the conjugate function consists of \(\mathbf y\in\mathbb R^d\) for which the supremum is finite. From the definition of conjugate function, we immediately obtain the inequality [ f(x) + f^*(y)x^{}y,x, y. ] This is called Fenchel’s inequality. If \(f\) is proper, convex, and lower semicontinuous, then the conjugate of the conjugate of a convex function is the original function, i.e., \((f^*)^*=f\).
If \(f : \mathbb{R}^d \to \mathbb{R}\) is a strictly convex and differentiable function, its Fenchel conjugate reduces to the Legendre conjugate (also known as the Legendre transform), defined by
\[ f^*(\mathbf{y}) = \mathbf{x}(\mathbf{y})^{\top} \mathbf{y} - f(\mathbf{x}(\mathbf{y})), \]
where \(\mathbf{x}(\mathbf{y}) = \arg\min_{\mathbf{x}} \left( \mathbf{x}^{\top} \mathbf{y} - f(\mathbf{x}) \right)\) is the unique solution to the first-order optimality condition \(\nabla f(\mathbf{x}) = \mathbf{y}\).
Definition 1.8 (Legendre function).
Let \(f:\mathbb{R}^d \to \mathbb{R}\cup\{+\infty\}\) be a proper, lower semicontinuous, convex function with \(\operatorname{int}(\operatorname{dom} f)\neq\emptyset\). The function \(f\) is called a Legendre function if it satisfies:
- \(f\) is differentiable on \(\operatorname{int}(\operatorname{dom} f)\), and for any sequence \(\{\mathbf{x}_k\}\subset \operatorname{int}(\operatorname{dom} f)\) with \(\mathbf{x}_k\) converging to a boundary point of \(\operatorname{dom} f\), we have \(\|\nabla f(\mathbf{x}_k)\|\to\infty\).
- \(f\) is strictly convex on every convex subset of \(\operatorname{dom}(\partial f)\).
If \(f\) is a Legendre function, its Fenchel conjugate reduces to the Legendre transform, defined by
\[\begin{equation*} f^*(\mathbf{y}) = \mathbf{x}(\mathbf{y})^{\top} \mathbf{y} - f(\mathbf{x}(\mathbf{y})), \end{equation*}\]
where \(\mathbf{x}(\mathbf{y}) = \arg\min_{\mathbf{x}} \left( \mathbf{x}^{\top} \mathbf{y} - f(\mathbf{x}) \right)\) is the unique solution to the first-order optimality condition \(\nabla f(\mathbf{x}) = \mathbf{y}\).
Example 1.11: Conjugate of the Quadratic Function
Let \(f(\mathbf{x}) = \frac{1}{2} \|\mathbf{x}\|^2\). Then:
\[ f^*(\mathbf{y}) = \sup_{\mathbf{x}} \left\{ \mathbf{x}^{\top} \mathbf{y} - \frac{1}{2} \|\mathbf{x}\|_2^2 \right\} = \frac{1}{2} \|\mathbf{y}\|_2^2. \]
Example 1.12: Conjugate of the Squared Hinge
Let \(f(x) = \max(x, 0)^2\). Then:
\[ f^*(y) = \sup_{x} \left( x y - \max(x, 0)^2 \right) = \begin{cases} \frac{y^2}{4}, & y \geq 0 \\ \infty, & y < 0 \end{cases} \]
The Legendre transform is not defined in this case since \(f\) is not strictly convex.
Example 13: Log-sum-exp and Negative Entropy
Log-sum-exp and negative entropy are conjugates of each other. Please refer to Example 1.16.