5
$\begingroup$

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.

  • 0
    (actually, the inequality says more than that, but it **implies** that the derivative is increasing).2012-06-24

1 Answers 1

2

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.