Homework 9
Assigned Mon Apr 25, due Thurs May 5

Subgradients for Nonconvex Functions

See my notes for the necessary background.

  1. We say that x locally minimizes f if, for all sufficiently small z, f(x+z) ≥ f(x). Show that it follows that a necessary condition for x to locally minimize f is that 0 is in the regular subdifferential of f at x, immediately from the definition on the first page of the notes.
  2. Determine the regular subdifferential, the (general) subdifferential and the horizon subdifferential of the following functions of one variable at x=0:
    1. f(x)=|x| 3
    2. f(x)=|x| 1/3
    3. f(x)=a|x| where a is nonnegative real number
    4. f(x)=a|x| where a is a negative real number
    5. f(x)=x2sin(1/x) if x is nonzero, f(0)=0. You can check by using the definition of the derivative that f is differentiable at 0 with f′(0)=0, and you can get f′(x) at any other x by using the ordinary rules of calculus. Verify that f′ is not continuous at 0, and hence that f is not C1 at 0.
    Using the definition on p.6 of the notes, which of these 5 functions is regular at 0?
  3. Same questions for the following two functions of n variables, at x=0:
    1. f(x) = 3rd largest entry of x, assuming n ≥ 3 (see p. 3-5 of the notes)
    2. f(x) = largest entry of Ax, where A is any n by n matrix (use the chain rule on p.7 of the notes)
    Which of these 2 functions is regular at 0?
  • This is not a question, but a comment. The functions given above that are locally Lipschitz at 0 are the ones for which the horizon subdiffential consists only of 0, and for these functions, the Clarke subdifferential at 0 is simply the convex hull of the (general) subdifferential.