IMC 2002 · Day 2 · P12

Let $g(x) = f(x) - f(x_1) - \langle \nabla f(x_1), x - x_1 \rangle$. It is obvious that $g$ has the same properties. Moreover, $g(x_1) = \nabla g(x_1) = 0$ and, due to convexity, $g$ has 0 as the absolute minimum at $x_1$. Next we prove that $$\tag{2} g(x_2) \ge \frac{1}{2L} \|\nabla g(x_2)\|^2.$$ Let $y_0 = x_2 - \frac{1}{L} \|\nabla g(x_2)\|$

and $y(t) = y_0 + t (x_2 - y_0)$. Then $$\begin{align*} g(x_2) &= g(y_0) + \int_0^1 \langle \nabla g(y(t)),\ x_2 - y_0 \rangle\,dt = \\ &= g(y_0) + \langle \nabla g(x_2),\ x_2 - y_0 \rangle - \int_0^1 \langle \nabla g(x_2) - \nabla g(y(t)),\ x_2 - y_0 \rangle\,dt \ge \\ &\ge 0 + \frac{1}{L} \|\nabla g(x_2)\|^2 - \int_0^1 \|\nabla g(x_2) - \nabla g(y(t))\| \cdot \|x_2 - y_0\|\,dt \ge \\ &\ge \frac{1}{L} \|\nabla g(x_2)\|^2 - \|x_2 - y_0\| \int_0^1 L \|x_2 - y(t)\|\,dt = \\ &= \frac{1}{L} \|\nabla g(x_2)\|^2 - L \|x_2 - y_0\|^2 \int_0^1 t\,dt = \frac{1}{2L} \|\nabla g(x_2)\|^2. \end{align*}$$ Substituting the definition of $g$ into (2), we obtain $$f(x_2) - f(x_1) - \langle \nabla f(x_1),\ x_2 - x_1 \rangle \ge \frac{1}{2L} \|\nabla f(x_2) - \nabla f(x_1)\|^2,$$ $$\tag{3} \|\nabla f(x_2) - \nabla f(x_1)\|^2 \le 2L \langle \nabla f(x_1),\ x_1 - x_2 \rangle + 2L (f(x_2) - f(x_1)).$$ Exchanging variables $x_1$ and $x_2$, we have $$\tag{4} \|\nabla f(x_2) - \nabla f(x_1)\|^2 \le 2L \langle \nabla f(x_2),\ x_2 - x_1 \rangle + 2L (f(x_1) - f(x_2)).$$ The statement (1) is the average of (3) and (4).