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
    Is this homework? If so, what have you tried so far, and where are you stuck?2012-01-29
  • 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 proof if near trivial but I can't get through with it.2012-01-29

1 Answers 1

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

  • 1
    Thanks, Can you see any sense in this beyond algebric "magic"? missing squares in second line btw.2012-01-29
  • 0
    You can draw a picture for the dimension $1$.2012-01-30
  • 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