Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers 2

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|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
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 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
add comment

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|improve this answer
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 3:13
    
@littleO what does the global-minimum actually mean? What does it look geometrically? –  hhh Oct 26 '12 at 3:31
add comment

Your Answer

 
discard

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.