# Lipschitz-constant gradient implies bounded eigenvalues on Hessian

I've read in a few places that if we have a Lipschitz gradient

$$\|\nabla f(x) - \nabla f(y)\|\leq L\|x-y\|,\, \forall x,y,$$ we can equivalently say $\nabla^2f\preceq LI.$ But I'm having a hard time showing this. (Equivalently, I want to show $z^T \nabla^2f(x)z\leq z^TLIz=Lz^Tz,\forall\, x,z$.)

• @user147263 I have a question regarding his answer, When you use mean value theorem. You will get something like: $$\|\nabla f(x)-\nabla f(y)\|\le \|\nabla^2 f \| \|x-y\|$$ From this have can you judge whether $\|\nabla^2 f \| \le L$ or not? The equality in the cauchy schwarz may not be obtained? – Li haonan Mar 17 '18 at 21:44

This is not true as stated. For example, the function $f(x)=x|x|$ on the real line has Lipschitz gradient, but is not twice differentiable. Also, the function $f(x)=-x^4$ satisfies $f''\le LI$ with $L=0$, but its gradient is not Lipschitz continuous.
The two properties are equivalent for functions that are convex and twice differentiable. For such functions, $\nabla^2 f$ is a positive semidefinite matrix, so its norm is its largest eigenvalue. Hence, $$\nabla^2 f \preceq LI \iff \|\nabla^2 f\|\le L \iff \|\nabla f(x)-\nabla f(y)\|\le L\|x-y\|$$ where the last equivalence is based on the mean value theorem.
• Are you sure that the Lipschitz constant is preserved in the equivalence, or there is some factor depending on the dimension $n$ ($f:\mathbb R^n\to \mathbb R$) ? Thanks. – Svetoslav Mar 15 '16 at 19:09
• It's preserved. The mean value theorem is applied on the line passing through $x,y$, so the problem becomes one-dimensional. – user147263 Mar 15 '16 at 19:10
It is equivalent for $||\bigtriangledown ^2f(x)||_2 \leq L$ where $||\bigtriangledown ^2f(x)||_2$ means the maximum singular value.