Convexity and subgradients · Definition

Subgradient

continuous optimizationconvexity and subgradients

When a convex function has corners or kinks, the gradient does not exist at those points. The subgradient lets you keep using optimization ideas there.

Definition

The subgradient generalizes the gradient to convex functions that are not differentiable: at each point it is a vector g that gives an affine lower bound of f, that is, f(y) ≥ f(x) + gᵀ(y − x) for all y.

\[f(y) \geq f(x) + g^\top (y - x)\]

The set of all subgradients of f at x is called the subdifferential, \( \partial f(x) \). If f is differentiable at x, the subdifferential reduces to the single vector \( \{\nabla f(x)\} \). Moreover, for a convex function the subdifferential is always a convex set, and it is nonempty in the interior of the domain.

Take \( f(x) = |x| \). At \( x = 0 \), the subdifferential is the interval \( [-1, 1] \), because every slope in that range stays below the function. At \( x = 2 \), however, \( \partial f(2) = \{1\} \), the same as the gradient.

A typical mistake is to think the subgradient must be unique, like the gradient. At nondifferentiability points there are infinitely many subgradients, and picking an arbitrary one is not the same as computing a derivative, so any value at a corner is not enough.

Think about it

Why can the subdifferential of \( |x| \) at \( x = 0 \) not be a single number?

Because infinitely many lines through \( (0,0) \) stay below \( |x| \) (slopes between \( -1 \) and \( 1 \)), so the set has infinitely many elements.

Exercises 10

  1. What is the name of the set of all subgradients of f at x?
  2. If f is differentiable at x, what is the subdifferential of f at that point?
  3. For f(x) = |x|, what is the subdifferential at x = 0?
  4. If \( g_1 \) is a subgradient of f at \( x_1 \) and \( g_2 \) is one at \( x_2 \), with f convex, which inequality holds?
  5. What does it mean for g to be a subgradient of f at x?
  6. For f(x) = max(x, 0), what is the subdifferential at x = 0?
  7. For f(x) = 2|x| at x = 1, what is the subdifferential?
  8. Let f(x) = |x| + x. What is the subdifferential at x = 0?
  9. For f(x) = |x - 3| at x = 3, what subdifferential does f have?
  10. Let f(x) = max(x, 0) + 2·max(-x, 0) for x in R. What is the subdifferential at x = 0?

What comes next

References

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