I am trying to prove the following statement
Let $\phi: \mathbb{R}^p \to \mathbb{R}$ be a convex function whose gradient exists at any point. Then for any $x, y$ we have $f(y) – f(x) \geq \langle \nabla f(x), y – x \rangle$.
without geometric interpretations as hyperplanes and such. I take as definition of convexity of $f$ that $\{(x, r) \ | \ f(x) \leq r\}$ is convex.
Any tips?
Best Answer
Let $g(t)=f((1-t)x+ty)$ for $0\leq t \leq 1$. Since $f$ is convex, $g$ too is convex, so $g'$ exists and is non-decreasing. We have by the Mean Value Theorem:
$$ f(y)-f(x)=g(1)-g(0)=g'(c)\geq g'(0) $$
for some $c\in (0,1)$. If we differentiate $g$ at $0$, we get
$$ g'(0)=df_{x}(y-x)=\langle \nabla f(x),y-x \rangle. $$
As for why $g$ is convex, we have that $h\colon t\in \mathbb{R}\mapsto (1-t)x+ty=x+t(y-x)$ is an affine function (i.e. $h(t)-h(t')=(t-t')(y-x)$ is linear in $t-t'$), so $g=f\circ h$ is convex. This is because for $t,t'\in \mathbb{R}$, $\mu \in [0,1]$, we have $h((1-\mu)t+\mu t')=(1-\mu)h(t)+\mu h(t')$ (by direct computation), so $$ f(h((1-\mu)t+\mu t'))=f((1-\mu)h(t)+\mu h(t'))\leq (1-\mu)f(h(t))+\mu f(h(t')) $$
Hope this helps!