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\}. \]

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}\).

Example 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 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 in Section 1.4.