lower bound of a special type of convex functions Suppose $f$ is a convex, differentiable and $\|\nabla f(x)-\nabla f(y)\|\leq L\|x-y\|$. The minimum of $f$ is $0$. ($f$ may not be twice differentiable.)
How to show $f(x)\geq\frac{1}{2L}\|\nabla f(x)\|^2$, $\forall x$?
 A: I'll assume $f$ is defined on all of $\mathbb{R}^n$. Let $f^* = \inf_{y \in \mathbb{R}^n} f(y)$.  (You have told us that $f^* = 0$, but I prefer just to call it $f^*$.)
Because $\nabla f(x)$ is Lipschitz continuous with parameter $L$, we have the following quadratic upper bound on $f$:
\begin{equation}
f(y) \leq f(x) + \langle \nabla f(x),y - x \rangle + \frac{L}{2} \| y - x \|^2
\end{equation}
for all $x,y \in \mathbb{R}^n$.
It follows that
\begin{equation}
\inf_y \, f(y) \leq \inf_y \, f(x) + \langle \nabla f(x),y - x \rangle + \frac{L}{2} \| y - x \|^2
\end{equation}
for all $x \in \mathbb{R}^n$.
The infimum on the left hand side is just $f^*$.  The infimum on the right hand side is
$f(x) -\frac{1}{2L} \| \nabla f(x) \|^2$.  Thus we find that
\begin{align*}
& f^* \leq f(x) - \frac{1}{2L} \| \nabla f(x) \|^2 \\
\implies& f(x) - f^* \geq \frac{1}{2L} \| \nabla f(x) \|^2.
\end{align*}
This result appears in chapter 1 ("Gradient method") of Vandenberghe's 236c lecture notes (see slide 1-14 entitled "Quadratic upper bound").
A: I started this last night, but got stuck with the transition from the one dimensional example back to $f$. (A problem related  to the Pinot Grigio technique  I was using, I think.)
Let $\phi:\mathbb{R}\to [0,\infty)$ be convex, differentiable, $\phi'$ Lipschitz continuous with rank $L$. Then Taylor gives:
$\phi(y) = \phi(x)+\phi'(x)(y-x) + \int_x^y (\phi'(t)-\phi'(x) )dt \leq \phi(x)+\phi'(x)(y-x) + L\int_x^y |t-x|dt$. Integrating gives the bound $\phi(y) \leq \phi(x)+\phi'(x)(y-x) + \frac{L}{2} (y-x)^2$. By assumption $\phi(t) \geq 0$, so we have $\phi(x)+\phi'(x)(y-x) + \frac{L}{2} (y-x)^2 \geq 0$ for all $x,y$. Minimizing over $y$ gives $\phi(x) \geq \frac{1}{2L} (\phi'(x))^2$, which is basically the desired result.
To connect with $f$ above, choose $x\neq y$, and let $\phi(t) = \frac{f(y+t(x-y))}{\|x-y\|^2} $, then $\phi'(t) = \frac{\partial f(y+t(x-y))}{\partial x}\frac{(x-y)}{\|x-y\|^2}$, and a quick computation  shows $|\phi'(t)-\phi'(s)|\leq L|t-s|$. This gives $\phi(1) \geq \frac{1}{2L} (\phi'(1))^2$, or equivalently, $f(x) \geq \frac{1}{2L} |\frac{\partial f(x)}{\partial x}\frac{(x-y)}{\|x-y\|}|^2$ (for all $x\neq y$). Since $\|v\| = \max_{\|u\|=1} |v^T u|$, this gives the desired result $f(x) \geq \frac{1}{2L} \|\frac{\partial f(x)}{\partial x}\|^2$.
