1

For strongly convex functions, it is stated that for some $\mu>0$,

  1. $$f(y)\geq f(x)+\nabla f(x)^T(y−x)+\frac{\mu}{2}\|y−x\|^2, \quad \forall x,y.$$
  2. $$(\nabla f(x)−\nabla f(y))^T(x−y)≥\mu\|x−y\|^2, \quad \forall x,y.$$

How does one prove that 2) implies 1)?

postmortes
  • 6,338
user 89084w
  • 27
  • 1
    I've converted your post to MathJax but there were some areas where I had to guess at what you meant. In particular I'm not certain if the $\mu$s should all be squared or not. Please review and check that's what there is correct. (And also, please use MathJax when posting. There are guides on the site.) – postmortes Oct 03 '19 at 08:06
  • it has to be $\mu/2$ instead of $\mu^2$ – daw Oct 03 '19 at 10:03
  • @daw thanks! Fixed that now – postmortes Oct 03 '19 at 15:55

1 Answers1

2

Use Taylor expansion: Take $x,y$. Then $$\begin{split} f(y)& = f(x) + \int_0^1\nabla f(x + s(y-x))^T(y-x)\ ds \\ &= f(x) + \nabla f(x)^T(y-x)+ \int_0^1(\nabla f(x + s(y-x))-\nabla f(x))^T(y-x)\ ds\\ &\ge f(x) + \nabla f(x)^T(y-x)+ \int_0^1\mu s\|x-y\|^2\ ds\\ &= f(x) + \nabla f(x)^T(y-x)+ \frac\mu2 \|x-y\|^2. \end{split}$$

daw
  • 49,113
  • 2
  • 38
  • 76
  • Thanks. could you explain the first step? I looked at the Taylor's expansion for partials (https://en.wikipedia.org/wiki/Taylor%27s_theorem#Derivation_for_the_integral_form_of_the_remainder). Before the integral, there are 2 summations. What happened to these summations? – user 89084w Oct 08 '19 at 13:13
  • The first step is just the fundamental theorem applied to the function $t\mapsto f(x+t(y-x))$ – daw Oct 08 '19 at 13:55