Show that $ \| \nabla^2 f(x) \| \le L \implies \| \nabla f(x) - \nabla f(y) \| \le L \| x-y \| $

Question

$f$ is a twice differentiable function from $R^n $ to $R$. I want to show that $$ \| \nabla^2 f(x) \| \le L \implies \| \nabla f(x) - \nabla f(y) \| \le L \| x-y \| $$ for all $x,y \in R^n $ and $L \ge 0 \in R$

I know that based on the mean value theorem that $$ f(x) - f(y) = (\nabla f (z) )^T (x-y) \implies \| f(x) - f(y) \| \le \| \nabla f (z) \| \| x-y| $$ for some point z on the line going thru $x$ and $y$. But not sure how to utilize this.

Thanks!

Answer 1

Here is an outline:

Pick some $w$ and let $\phi(x) = w^T \nabla f(x)$.

Compute $\nabla \phi(x)$.

Apply the mean value theorem to $\phi$ to get $|w^T (\nabla f(x) - \nabla f(y) ) | \le L \|w\| \|x-y\|$. For fixed $x,y$ this holds for all $w$.

Choose $w$ appropriately to show that this implies the desired result.

Answer 2

Based on the hint given in the comment below:

From the mean value theorem we know that $$g(y) - g(x) = (\nabla g (z))^T (x-y) $$ for some $z$ on the line going thru $x$ and $y$.

Take $g(x) = w^T \nabla f(x) $ for an arbitrary $w \in R^n$ , observe that $$\nabla g(x)= \nabla^2 f(x) w$$ and have:

\begin{align*} &w^T(\nabla f(x) - \nabla g(y)) = (\nabla^2 f(z) w )^T (x-y) \\ & \implies \| w^T(\nabla f(x) - \nabla g(y)) \| \\ &= \| (\nabla^2 f(z) w )^T (x-y) \| \le \| w \| \| \nabla^2 f(z) \| \| x-y \|\\ & \le L \| w \| x-y \| \;\;\;\ (\text{using } \| \nabla^2 f(x) \| \le L) \\ \end{align*}

Take $w = \frac { \nabla f(x) - \nabla g(y) } {\| \nabla f(x) - \nabla g(y) \| } $, a unit vector and get

$$ \| \nabla f(x) - \nabla f(y) \| \le L \| x-y \| $$