Showing a twice differentiable function with positive hessian is convex.

Question

Let $f:\mathbb{R}^n\to\mathbb{R}$ be twice differentiable . If $f_{xx}( .)\geq 0$ for any $x\in\mathbb{R}^n$, then $f$ is convex.

I think they mean $f_{xx}(.)$ is a positive matrix. As, $f$ is twice differentiable, we can see for any $x, y\in \mathbb{R}^n$, there exist $\theta_1, \theta_2\in (0,1)$, satisfying $$f(y)=f(x)+f_x(x).(y-x)+\theta_1(y-x)^Tf_{xx}(x+\theta_1\theta_2(y-x)).(y-x).$$

Hence $f(y)-f(x)\geq f_x(x).(y-x).$

Using the fact $f_x(x).(y-x)=\lim_{\lambda\to1}\frac{f(\lambda x+(1-\lambda)y)-f(x)}{1-\lambda}$, I get $$f(y)-f(x)\geq \lim_{\lambda\to1}\frac{f(\lambda x+(1-\lambda)y)-f(x)}{1-\lambda}.$$

Now if I don't consider the $\lim_{\lambda\to1}$, then by some calculation, I can get

$$\lambda f(x)-(1-\lambda)f(y)\geq f(\lambda x+(1-\lambda)y).$$

However, I'm not sure if this is a valid thought. Thank you.

Answer 1

From the inequality you derived we obtain $$ f(x) - f(\lambda x+(1-\lambda)y) \ge f'(\lambda x +(1-\lambda)y)(1-\lambda)(x-y)\\ f(y) - f(\lambda x+(1-\lambda)y) \ge f'(\lambda x +(1-\lambda)y)\lambda (y-x) $$ Multiplying the first inequality with $\lambda$, the second with $1-\lambda$, adding both yields $$ \lambda f(x) + (1-\lambda)f(y) - f(\lambda x+(1-\lambda)y) \ge 0 $$

Answer 2

I'll use the convention that the gradient is a column vector. (This convention is often used in optimization.)

Let $x,y \in \mathbb R^n$ and define $g:[0,1] \to \mathbb R$ by $g(t) = f(x + t(y-x))$. From the chain rule, $g'(t) = (y-x)^T \nabla f(x + t(y-x))$ and $g''(t)=(y-x)^T \nabla^2 f(x+t(y-x))(y-x) \geq 0$. (The last inequality uses the fact that the Hessian is positive semidefinite.)

This shows that $g'$ is a nondecreasing function, which implies that $g$ is convex. It follows that $f$ is convex.