Suppose I have
$f: \mathbb{R}^n \to \mathbb{R}_\infty$ which is twice continuously differentiable, on some convex set C, which is open.
How can I prove that $f$ is convex over C, iff the hessian ($\nabla^2 f(x))$ is positive semidefinite $\forall x \in C$ ?
Best Answer
If the hessian is positive semidefinite, and $x_1,x_2\in C$, we want to show that $f(tx_1 + (1-t)x_2) \leq tf(x_1) + (1-t)f(x_2)$. Consider $g(t) = f(tx_1 + (1-t)x_2)$. Write the condition you want to prove of $f$ in terms of $g$. Now, Can you find the second derivative of $g(t)$?
Use the fact that the hessian is positive semidefinite to show that $g''(t)\geq 0$, and now use the Taylor expansion of $g(t)$ around $t=0$ and $t=1$: this gives $$g(0) = g(t) + (0-t)g'(t) + \dfrac{(0-t)^2}{2}g''(\xi) \geq g(t) - tg'(t)$$ and $$g(1) = g(t) + (1-t)g'(t) + \dfrac{(1-t)^2}{2}g''(\xi)\geq g(t) + (1-t)g'(t)$$
Now, this implies $g(t) \leq tg(0) + (1-t)g(1)$, which is what you want.