Strong convexity and Lipschitz

Solution 1:

Suppose that $f:\mathbb{R}^n\to\mathbb{R}$ is strongly convex with the modulus $\lambda$ and it is differentiable with its derivative satisfying $$ \textbf{(I)}\quad\quad\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|, \quad \forall x,y\in \mathbb{R}^n. $$ Then, we have $\lambda \leq L$.

Proof.

Step 1. For all $x,y\in \mathbb{R}^n$ $$ \textbf{(II)}\quad\quad f(x)-f(y)\geq \langle\nabla f(y), x-y\rangle+(\lambda/2)\|x-y\|^2. $$ By the strong convexity of $f$ $$ f(\alpha x+(1-\alpha)y)\leq \alpha f(x)+(1-\alpha)f(y)-\lambda\alpha(1-\alpha)\|x-y\|^2/2. $$ for all $\alpha\in (0,1)$. It implies that $$ f(x)-f(y)\geq\frac{f(y+\alpha(x-y))-f(y)}{\alpha}+\lambda(1-\alpha)\|x-y\|^2/2. $$ Letting $\alpha\to 0^+$, we obtain (I).

Step 2. For all $x,y\in \mathbb{R}^n$ $$ \textbf{(III)}\quad\quad\langle \nabla f(x)-\nabla f(x), x-y\rangle\geq \lambda \|x-y\|^2. $$ Applying inequality (II) we deduce $$ f(x)-f(y)\geq \langle\nabla f(y), x-y\rangle+(\lambda/2)\|x-y\|^2, $$ $$ f(y)-f(x)\geq \langle\nabla f(x), y-x\rangle+(\lambda/2)\|x-y\|^2. $$ Adding two inequalities we get (II).

Step 3. $\quad\lambda\leq L$

Choosing $x,y\in\mathbb{R}^n$ such that $x\ne y$. By (I), (III), and the Cauchy Schwarz $$ \lambda \|x-y\|^2\leq \langle \nabla f(x)-\nabla f(x), x-y\rangle\leq\|\nabla f(x)-\nabla f(x)\|\|x-y\|\leq L\|x-y\|^2. $$ Since $x\ne y$, this follows that $\lambda\leq L$.

Solution 2:

Assuming that the definitions are what I think they are, the two requirements are $$\begin{aligned} \|\nabla f(y)-\nabla f(x)\|&\ge\lambda\|y-z\|&&\text{$f$ is $\lambda$-convex}\\ \|\nabla f(y)-\nabla f(x)\|&\le L\|y-z\|&&\text{$\nabla f$ is $L$-Lipschitz} \end{aligned} $$ for all $y$, $z$. Really, I insist that you draw the inevitable conclusion without my help.