# Equivalence of statements regarding convex function with Lipschitz continuous gradient

I came into a practice problem on Lipschitz continuous gradient.

Given convex and twice continuously differentiable $$f$$, prove the following statements are equivalent.

1. $$\nabla f$$ is Lipschitz continuous with constant $$L$$.

2. $$(\nabla f(x) − \nabla f(y))^T (x − y) \leq L \| x − y \|_2^2$$ for all $$x$$, $$y$$.

$$1\to2$$ it can be tackled by the Cauchy-Schwartz inequality. However, I can not figure $$2\to1$$ out.

• Are you sure that the LHS of the second inequality is not $(\triangledown f(x) − \triangledown f(y))^T (\triangledown f(x) −\triangledown f(y))$? – user88923 May 8 '19 at 5:32
• Hi, I checked the original statement. The statement indeed is as correct here. – JC Wang May 8 '19 at 18:41

It easy to check that 2. is equivalent to the monotonicity of the gradient of the function $$g:x\mapsto \frac L2 \|x\|_2^2-f(x)$$, which is equivalent to the convexity of $$g$$.
The Hessian of $$g$$ at $$x$$ is $$H(g)(x)=LI-H(f)(x)$$ where $$I$$ denotes the identity matrix. Let $$\operatorname{spec}(A)$$ denote the eigenvalues of any matrix $$A$$. Note that $$\operatorname{spec}(LI-H(f)(x)) = L-\operatorname{spec}(H(f)(x))$$, and since $$g$$ is convex, $$\operatorname{spec}(LI-H(f)(x)) \subset [0,\infty)$$, hence $$\operatorname{spec}(H(f)(x))\subset (-\infty,L]$$. Convexity of $$f$$ implies the refinement $$\operatorname{spec}(H(f)(x))\subset [0,L]$$.
Let $$h:[0,1]\to \mathbb R^n, t\mapsto \nabla(f)(x+t(y-x))$$. $$h$$ is differentiable and \begin{aligned}\|h'(t)\|_2=\|H(f)(x+t(y-x))(y-x)\|_2 &\leq \max \left[\operatorname{spec}(H(f)(x+t(y-x)))\right] \|y-x\|_2\\ &\leq L \|y-x\|_2 \end{aligned}
The mean value inequality for vector-valued functions yields $$\|h(1)-h(0)\|\leq L \|y-x\|_2$$, hence the claim.