Lower bound for Strongly convex and Lipschitz gradient function I was reading this paper but could not understand one of it's condition. It says a function $f(x)$ is twice differentiable and strongly convex with parameter $m$ and Lipschitz continuous gradient with parameter $M$ and $M\geq m$. Then:
$$(x-y)^T(\nabla f(x)-\nabla f(y) \geq \frac{mM}{m+M} \lVert x-y \rVert^2+\frac{1}{m+M}\lVert \nabla f(x)-\nabla f(y) \rVert ^2$$ 
I know that if $f$ is strongly convex and Lipshcitz continuous gradient, then :
$$(x-y)^T(\nabla f(x)-\nabla f(y)) \geq m \rVert x-y\lVert ^2$$
and 
$$(x-y)^T(\nabla f(x)-\nabla f(y)) \geq \frac{1}{M} \lVert \nabla f(x)-\nabla f(y) \rVert  ^2 $$. I tried multiply each by $M$ and $m$ and adding up but that didn't quite work.
 A: I emailed the author of the paper, here is the reply I got: "It is a non trivial result which is often used in convex optimization. I guess you can find it in Nesterov's book
Introductory Lectures on Convex Optimization: A Basic Course.​ Theorem 2.1.12"
A: Are you sure about the coefficient within the second term on the right hand side?
As you mentioned the strong convexity means
$$(x-y)\cdot (\nabla f(x) - \nabla f(y) ) \ge m ||x-y||^2, $$
and the Lipschitz property of the gradient means
$$ ||\nabla f(x) - \nabla f(y)|| \le M ||x-y||. $$
Combining both gives:
$$ (x-y) \cdot (\nabla f(x) - \nabla f(y)) 
= m\frac{m+M}{m+M} ||x-y||^2 
\ge \frac{mM}{m+M} ||x-y||^2  + \frac{m^2}{m+M} ||x-y||^2 
\ge \frac{mM}{m+M} ||x-y||^2  + \frac{m^2}{M^2(m+M)} ||\nabla f(x) - \nabla f(y)||^2. $$
A: you can define $g(x)=f(x)-\frac{m}{2}\|x\|^2$, which is convex because $f$ is strongly convex with constant $m$. The function $g$ also satisfies
$$g(y)-g(x)-\langle\nabla g(x),y-x\rangle = f(y)-f(x)-\langle\nabla f(x),y-x\rangle-\frac{m}{2}\|x-y\|^2 
 \le \frac{M-m}{2}\|x-y\|^2,$$
because $\nabla f$ is Lipschitz-continuous with constant $M$. It follows that $\nabla g$ is Lipschitz-continuous with constant $M-m$ and cocoercive with constant $(M-m)^{-1}$ (these three implications are actually equivalences, as shown in Theorem 18.15 in the book of Bauschke and Combettes), which means that
$$\langle \nabla g(x)-\nabla g(y),x-y\rangle\ge\frac{1}{M-m}\|\nabla g(x)-\nabla g(y)\|^2.$$
Rewriting this back in terms of $f$, yields the desired inequality.
I hope this helps.
