Section 1.2: Verification of Convexity
In practice, directly applying the definition of convexity can be challenging when proving that a function is convex. The following rules offer practical tools to simplify the verification process.
Twice Differentiable Functions
If a function \(f(\mathbf{x})\) is twice differentiable, then it is convex if and only if
\[ \nabla^2 f(\mathbf{x}) \succeq 0, \quad \forall \mathbf{x}, \]
i.e., its Hessian is positive semidefinite everywhere.
Examples:
We can use the above rule to verify the convexity of the following functions.
Example 9: Log-Sum-Exp Function
\[ \ell(\mathbf{y}) = \log\left(\sum_{i=1}^K \exp(y_i)\right), \quad \mathbf{y} \in \mathbb{R}^K. \]
This function is convex due to the positive semidefiniteness of its Hessian.
Example 10: Negative Entropy
\[ \varphi(\mathbf{p}) = \sum_{i=1}^n p_i \log p_i \]
is a convex function of \(\mathbf{p} \in \Delta_n\), where \(\Delta_n\) denotes the probability simplex.
Operations that Preserve Convexity
The following operations preserve convexity:
Affine Composition:
If \(f\) is convex, then \(f(A\mathbf{x} + \mathbf{b})\) is convex for any matrix \(A\) and vector \(\mathbf{b}\).Non-Negative Weighted Sums:
If \(f_i\) is convex for all \(i\), and \(\alpha_i \geq 0\), then\[ f(\mathbf{x}) = \sum_i \alpha_i f_i(\mathbf{x}) \]
is convex.
Pointwise Maximum:
If \(g(\mathbf{x}, \mathbf{y})\) is convex in \(\mathbf{x}\) for all \(\mathbf{y}\), then\[ f(\mathbf{x}) = \max_{\mathbf{y}} g(\mathbf{x}, \mathbf{y}) \]
is convex.
Function Composition:
The composition \(h(\mathbf{x}) = f(g(\mathbf{x}))\) is convex if one of the following holds:- \(f\) is convex and non-decreasing,
and \(g(\mathbf{x})\) is convex.
- \(f\) is convex and non-increasing, and \(g(\mathbf{x})\) is concave.
- \(f\) is convex and non-decreasing,
and \(g(\mathbf{x})\) is convex.