3
$\begingroup$

In these notes (section 2.3), it is stated that:

A point $x^*$ is a minimizer of a function $f$ (not necessarily convex) if and only if $f$ is subdifferentiable at $x^*$ and $0 \in\partial f(x^*).$

Could anybody provide me with references for a proof of the above statement?

Is there a reference where we can learn more about subgradients of non-convex functions? In Section 3. Calculus of subgradients of the above notes,many properties of subgradients are presented for convex functions. I would like to know which ones among these properties still hold for non-convex functions.

Thank you in advance!

$\endgroup$
6
$\begingroup$

The fact that $x^*$ is a (global!) minimizer of $f$ if and only if $0\in\partial f(x^*)$ is already fully explained in the notes you linked to -- it's really that simple, but here's the argument again for the sake of completeness. Assume that $x^*$ is a global minimizer of $f$. Then, by definition, $$ f(x) - f(x^*) \geq 0 = 0^T (x-x^*) \qquad\text{for any }x\in\mathbb{R}^n, $$ which is exactly the definition of the convex subdifferential (and subdifferentiability). For the other direction, you just swap the last equality around to see that one definition implies the other. (Note that this argument only works for global minimizers -- this is where the convexity of $f$ really comes in, because for convex functions, every minimizer is a global minimizer).

As to the other properties for non-convex functions: The short answer is none. Note that the reverse direction assumes that $f$ is subdifferentiable, i.e., that the set $\partial f(x^*)$ is non-empty. This doesn't sound like much (indeed, it's always true for any (locally finite) convex function), but it pretty much only holds for convex functions. In fact, you can show that if the subdifferential is non-empty everywhere, then $f$ is convex (see https://math.stackexchange.com/q/1499059). So all the other properties -- which are statements about some elements of the subdifferential -- are in general true only in the vacuous sense (as statements about the empty set).

However, there are further generalizations of subdifferentials for non-convex functions, which are non-empty for larger (but still restricted) classes of functions and admit similar properties (in particular, necessary optimality conditions). Needless to say, the larger the class, the trickier they are to work with. One prominent example is Clarke's generalized gradient of locally Lipschitz continuous functions (see, e.g. Chapter 10 Clarke, Functional Analysis, Calculus of Variations and Optimal Control, Springer 2013). You can find even more generalized derivatives in Schirotzek, Nonsmooth analysis, Springer 2007.

$\endgroup$
  • $\begingroup$ Just came across this answer again. The references are very helpful. Great answer! $\endgroup$ – Khue May 13 '17 at 12:06
1
$\begingroup$

In terms of the subdifferential definition used in the notes, the statement is immediate by definition.

For a more general notion of subdifferential, Proposition 2.3.2 on page 38 of Clarke, F. H. (1990), "Optimization and Nonsmooth Analysis" says:

If $f$ attains a local minimum or maximum at $x$, then $0\in \partial f (x).$

$\endgroup$
  • 1
    $\begingroup$ That's a different subdifferential (although it coincides with the convex subdifferential if $f$ is convex). And you just disproved the opposite direction :) $\endgroup$ – Christian Clason Apr 22 '16 at 19:06
  • $\begingroup$ I agree that one should not mix different definition of subdifferential -- thanks! I have updated my answer. $\endgroup$ – user3605620 Apr 22 '16 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.