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.

The definition of strongly convex from Wikipedia:

It is not necessary for a function to be differentiable in order to be strongly convex. A third definition for a strongly convex function, with parameter $m$, is that, for all $x$, $y$ in the domain and $t\in [0,1]$, $$f(tx+(1-t)y) \le t f(x)+(1-t)f(y) - \frac{1}{2} m t(1-t) \|x-y\|_2^2.$$

Prove that the 2-norm squared $f(w) = m\|w\|^2 $ is m strongly convex

I have so far tried to use the triangle inequality but I cannot derive that last negative term.

share|improve this question
    
Is this homework? If so, what have you tried so far, and where are you stuck? –  Lopsy Jan 29 '12 at 20:14
    
Sorry, my bad. I edited the question. This isn't homework, I met this claim in lecture notes along with a promise that the proof if near trivial but I can't get through with it. –  Leo Jan 29 '12 at 20:34
add comment

1 Answer

up vote 5 down vote accepted

The key is to use the fact that the $2$-norm comes from an inner product. We have \begin{align*} f(tx+(1-t)y)-t(f(x)-(1-t)f(y)&=mt^2||x||^2+2mt(1-t)\langle x,y\rangle+m(1-t)^2||y||^2\\ & - mt||x||^2-m(1-t)||y||^2\\ &=mt(t-1)||x||^2+m(1-t)(1-t-1)||y||\\ &+2mt(1-t)\langle x,y\rangle\\ &=-mt(1-t)||x||^2+2mt(1-t)\langle x,y\rangle -mt(1-t)||y||^2\\ &=-mt(1-t)(||x||^2-2\langle x,y\rangle+||y||^2)\\ &=-mt(1-t)||x-y||^2\\ &\leq -\frac 12mt(1-t)||x-y||^2 \end{align*} since $mt(1-t)||x-y||^2\geq 0$.

share|improve this answer
    
Thanks, Can you see any sense in this beyond algebric "magic"? missing squares in second line btw. –  Leo Jan 29 '12 at 23:55
    
You can draw a picture for the dimension $1$. –  Davide Giraudo Jan 30 '12 at 10:10
1  
The picture of x^2 doesn't provide much insight. Simple convexity 1d pictures explain very well but it's hard if not impossible to guess strong convexity from a picture. I can't imagine for example how picturing this could guide the derivation of the proof. –  Leo Jan 30 '12 at 11:55
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.