Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I haven't understood this theorem "$x^*$ is global minimum iff $\bar 0\in \partial f(x^*)$". What does it mean? Visually?

enter image description here

P.s. Studying Nonlinear-optimization -course, 2.3139.

share|cite|improve this question
up vote 2 down vote accepted

If $f$ is a convex function, to say that $g \in \partial f(x)$ means that \begin{equation*} f(y) \geq f(x) + \langle g, y - x \rangle \end{equation*} for all $y$.

For example, let $f(x) = |x|$. $f$ is not differentiable at $0$, but $f$ is convex, and $f$ has a subdifferential $\partial f(0)$.

And you can see that $0 \in \partial f(0)$ in this example.

So... note that if $f$ is convex then \begin{align*} & x \text{ is a minimizer of } f \\ \iff & f(y) \geq f(x) \, \forall \, y \\ \iff & f(y) \geq f(x) + \langle 0 , y - x \rangle \, \forall \, y \\ \iff & 0 \in \partial f (x). \end{align*}

share|cite|improve this answer
What does it mean "f has a subdifferential ∂f(0)"? I got $|x|\leq g\cdot x$ which is true when $x=0$. Is my answer correct? I am wondering what I meant when I wrote "subgradient not unique in the picture", thinking. +1 thank you! – hhh Oct 26 '12 at 1:25
Keep in mind that for a convex function $f$, $\partial f(x)$ is equal (by definition) to $\{ g \mid f(y) \geq f(x) + \langle g, y - x \rangle \, \forall \, y\}$. In the example where $f(x) = |x|$, $\partial f(0)$ contains all real numbers between $-1$ and $1$ (inclusive). – littleO Oct 26 '12 at 3:08
The reason that $0 \in \partial f(0)$ (when $f(x) = |x|$) is that $|y| \geq |0| + \langle g, y - 0 \rangle$ for all $y$ when $g = 0$. (Actually this holds for any value of $g$ between $-1$ and $1$.) – littleO Oct 26 '12 at 3:14

I can only understand this in the format:

Suppose $f(x)$ is a convex function. Suppose its Hessian matrix $\nabla^2 f$ is positively definite i.e. its square-form $x \left(\nabla^2 f \right)x^T$ is positive. Now $x^*$ is global minimum iff $\bar 0\in \partial f(x^*)$".

This is understandable because it would mean that the subgradient has a point in which $\nabla f =0$.

Video recommendation

Very good video in point 18-26.00 in Stanford here.

enter image description here

share|cite|improve this answer
$f$ may not be differentiable, though. Even if a convex function $f$ is not differentiable at $x$, $f$ may at least have one or more subgradients at $x$. – littleO Oct 26 '12 at 3:13
@littleO what does the global-minimum actually mean? What does it look geometrically? – hhh Oct 26 '12 at 3:31

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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