0

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.

hhh
  • 5,469

2 Answers2

3

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*}

littleO
  • 51,938
  • 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 01:25
  • 1
    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 03: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 03:14
0

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

Community
  • 1
hhh
  • 5,469
  • 1
    $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 03:13
  • @littleO what does the global-minimum actually mean? What does it look geometrically? – hhh Oct 26 '12 at 03:31