7
$\begingroup$

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.

  • 0
    Sorry, my bad. I edited the question. This isn't homework, I met this claim in lecture notes along with a promise that the proo$f$ if near trivial but I can't get through with it.2012-01-29

2 Answers 2

8

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$.

  • 2
    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.2012-01-30