Convexity and subgradients · Definition

Convexity and the Hessian

continuous optimizationconvexity and subgradients

Before you start you need to know

When a function has second derivatives, convexity can be checked without comparing chords. It suffices to examine the curvature at each point through the Hessian.

Definition

Criterion characterizing convexity of a twice differentiable function through positive semidefiniteness of its Hessian matrix \(\nabla^2 f(x)\) at every point of the domain.

\[f \text{ convexa} \iff \nabla^2 f(x) \succeq 0 \ \forall x \in \operatorname{dom} f\]

If \(f\) is twice differentiable and its domain \(\operatorname{dom} f\) is convex, then \(f\) is convex if and only if \(\nabla^2 f(x) \succeq 0\) for all \(x\). If the inequality is strict everywhere, \(f\) is strictly convex, although the converse does not always hold. Semidefiniteness is checked with nonnegative eigenvalues or nonnegative principal minors.

Consider \(f(x,y)=x^2+xy+y^2\). Its second derivatives give \(\nabla^2 f=\begin{pmatrix}2&1\\1&2\end{pmatrix}\), whose eigenvalues are \(1\) and \(3\), both positive. Hence \(f\) is strictly convex on \(\mathbb{R}^2\).

A typical mistake is concluding convexity by looking only at the Hessian entries, for example that they are positive. A matrix with all positive entries can still have a negative eigenvalue, such as \(\begin{pmatrix}1&3\\3&1\end{pmatrix}\), and then it is not positive semidefinite.

Think about it

Can a strictly convex function have a zero Hessian at some point?

Yes. For example, \(f(x)=x^4\) is strictly convex and \(f''(0)=0\), so strict positivity of the Hessian is not necessary.

Exercises 10

  1. What condition on the Hessian guarantees that \(f\) is convex?
  2. If \(\nabla^2 f(x)\) is negative semidefinite everywhere, what kind of function is \(f\)?
  3. For \(f(x)=x^2\), what is its Hessian \(\nabla^2 f(x)\)?
  4. What does it mean for a symmetric matrix to be positive semidefinite?
  5. What kind of set must the domain of \(f\) be to apply the Hessian criterion?
  6. Compute the Hessian of \(f(x,y)=x^2+3xy\) and determine whether it is positive semidefinite.
  7. For which values of \(a\) is \(f(x,y)=x^2+axy+y^2\) convex on \(\mathbb{R}^2\)?
  8. Let \(f(x,y)=e^{x}+y^2\). Is \(f\) convex on \(\mathbb{R}^2\)?
  9. Let \(f(x,y)=x^3+y^2\). What can be concluded about the convexity of \(f\) on \(\{x\geq 0\}\)?
  10. Let \(f(x,y)=x^2-y^2+2xy\). Determine whether \(f\) is convex on \(\mathbb{R}^2\) and justify using the Hessian.

References

  • Stephen Boyd, Lieven Vandenberghe, Convex Optimization, 1st edition, Cambridge University Press, 2004.
  • Jorge Nocedal, Stephen J. Wright, Numerical Optimization, 2nd edition, Springer, 2006.