# $f(y) \leq f(x)+\nabla f(x)\cdot (y-x)$ and $f(x)\geq 0$ implies that $f$ is constant.

Here is the question.

Suppose that $f: \mathbb R^n \rightarrow \mathbb R$ has two derivatives and the associated hessian matrix is negative semidefinite on all of $\mathbb R^n$.

Show that for any $x,y\in \mathbb R^n$

$$f(y) \leq f(x)+\nabla f(x)\cdot (y-x)$$

I can show this using Taylor's formula. But the question also says:

If in addition $f(x)\geq 0$ for all $x\in \mathbb R^n$ then show that f must be constant. Can you help me on the second part. I know that I need to show that $\nabla f(x)=0, \forall x\in \mathbb R^n$.

Any hints?

-
do you mean the Hessian associated with $f$ is negative-simidefinite? – Laura Jan 10 '13 at 8:07
@Tai:Sorry yes, that's what I meant. I will edit this. – Jack Dawkins Jan 10 '13 at 8:11
Hint: Assume that $\nabla f(x)$ is not zero for some $x$. Fix one such $x$, and set $y = x + t \nabla f (x)$. Can you pick good $t$ to make $f(y)$ negative? – user27126 Jan 10 '13 at 8:25

Assume $\nabla f(x) = c \neq 0$. Then, we have $\forall x,y$ $$\tag{1} 0\leq f(y) \leq f(x) + c \cdot (y-x).$$
There has to be a point $x$ where $f(x) >0$ (otherwise $f(x) = 0$ and the theorem is proven). Now take $$y = x- \frac{2 f(x) }{\lVert c\rVert^2} c .$$ Plug it in (1) and enjoy the contradiction.
If $f(y)\geq 0$ for all $y\in\mathbb{R}^n$, then by $f(y) \leq f(x)+\nabla f(x)\cdot (y-x)$, we have $$\tag{1}0\leq f(x)+\nabla f(x)\cdot (y-x)\mbox{ for all }x,y\in\mathbb{R}^n.$$ Fixed any $x\in\mathbb{R}^n$. Suppose $\nabla f(x)\neq 0$, then we can choose $$y=x+\frac{\nabla f(x)}{|\nabla f(x)|^2}[-2f(x)-1]\in\mathbb{R}^n$$ such that $$\tag{2}\nabla f(x)\cdot (y-x)=-2f(x)-1.$$ Combining $(1)$ and $(2)$, we have $0\leq f(x)+(-2f(x)-1)$, or $f(x)\leq -1$, which contradicts to $f(x)\geq 0$. Therefore, we must have $\nabla f(x)=0$. Since $x$ is arbitrary, we have $\nabla f(x)=0$ for all $x\in\mathbb{R}^n$.