# Continuously differentiable with constraint on gradient implies the function is convex

I am not sure what the relevant theorems for this problem are. I have been searching through Rudin for some hints, but I have come up short. This is an example question for an exam, so not homework.

Can anyone point me in the right direction? Thanks.

A function $f: \mathbb{R}^n \to \mathbb{R}$ is called convex if $f$ satifies $$f(\alpha x + (1 - \alpha)y) \le \alpha f(x) + (1 - \alpha)f(y) \quad \forall x, y \in \mathbb{R}^n,\ 0 \le \alpha \le 1.$$ Assume that $f$ is continuously differentiable and that for some constant $c > 0$, the gradient $$(\nabla f(x) - \nabla f(y)) \cdot (x - y) \ge c(x - y) \cdot (x - y), \quad \forall x, y \in \mathbb{R}^n,$$ where $\cdot$ denotes the dot product. Show that $f$ is convex.

-
Hint: convexity is determined by restrictions to lines. For such a restriction, the gradient inequality simply says that the derivative is increasing. –  user31373 Jun 24 '12 at 21:45
(actually, the inequality says more than that, but it implies that the derivative is increasing). –  user31373 Jun 24 '12 at 21:59

Let $x,y\in\mathbb R^n$ and let $\varphi:[0,1]\rightarrow\mathbb R$ defined by $\delta\mapsto f(x+\delta(y-x))$.
Check that $\varphi'(\delta)=(\nabla f(x+\delta(y-x)))\cdot(y-x)$.
So for all $\delta\in]0,1]$, $\varphi'(\delta)-\varphi'(0)=\frac{1}{\delta}(\nabla f(x+\delta(y-x))-\nabla f(x))\cdot(\delta(y-x))\ge\delta c \|y-x\|^2$ by your hypothesis.
Notice that the inequality is also true for $\delta=0$.
By integration : $$\varphi(1)-\varphi(0)\ge\int_0^1\varphi'(0)+\delta c \|y-x\|^2d\delta=\varphi'(0)+\frac{c}{2}\|y-x\|^2\ge\varphi'(0)$$ And so $$f(y)\ge f(x)+\nabla f(x)\cdot(y-x)$$
So for all $x,y\in\mathbb R^n$, $f(y)\ge f(x)+\nabla f(x)\cdot(y-x)$.
Write this last inequality for $(x+\delta(y-x),y)$ and for $(x+\delta(y-x),x)$ with $\delta\in[0,1]$ and $x,y\in\mathbb R^n$, so $$f(y)\ge f(x+\delta(y-x))+(1-\delta)\nabla f(x+\delta(y-x))\cdot(y-x)$$ $$f(x)\ge f(x+\delta(y-x))-\delta\nabla f(x+\delta(y-x))\cdot(y-x)$$ Multiply the first line by $\delta$ the second line by $1-\delta$, then sum, and you'll get : $$\delta f(y)+(1-\delta)f(x)\ge f(x+\delta(y-x))=f((1-\delta)x+\delta y)$$ So $f$ is convex.