Section 1.2: Verification of Convexity

In practice, directly applying the definition of convexity or verifying the first-order condition of convexity can be challenging when proving that a function is convex. The following rules offer practical tools to simplify the verification process.

Second-order Condition for 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 1.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. \]

Its Hessian matrix is given by \[H = \text{diag}(\mathbf{p}) - \mathbf{p}\mathbf{p}^T,\] where \(\mathbf{p}\) is the vector of softmax probabilities with components \(p_i = \frac{\exp(y_i)}{\sum_{k=1}^K \exp(y_k)}\). It is positive semidefinite as \(\mathbf v^{\top}H\mathbf v = \sum_{i=1}^Kp_i v_i^2 - (\sum_{i=1}^Kp_iv_i)^2\geq 0\) due to Cauchy-Schwarz inequality.

Example 1.10: Negative Entropy

\[ \varphi(\mathbf{p}) = \sum_{i=1}^n p_i \log p_i, \]

where \(\mathbf p \in \Delta_n\) is a probability vector. Its Hessian matrix is \[H = \text{diag}(1/\mathbf p)\] is positive definite.

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.

To quickly verify this, we compute the Hessian matrix assuming that both \(f\) and \(g\) are twice-differentiable: \[ \nabla^2 h(\mathbf x) =f'(g(\mathbf x)) \nabla^2 g(\mathbf x) + f''(g(\mathbf x)) \nabla g(\mathbf x)\nabla g(\mathbf x)^{\top}, \] which is positive semi-definite under either of the above two conditions.

← Go Back