# Using Taylor's theorem and Lagrange form of the reminder to prove the second order condition for convexity

I try to prove the second order condition for convexity.

So far' I've done the following:

First, I prove second order => convexity:

Let $f$ be a function with positive semi-definite Hessian. Using second order Taylor expansion I have:

$f(y) = f(x)+\nabla f(x)^T(y-x)+(y-x)^T \nabla^2f(x+a(y-x))(y-x)$ for some value of $a \in [0,1]$. Let's note this by (*).

Now, since the Hessian is positive semi-definite, $(y-x)^T \nabla ^2f(x+a(y-x))(y-x) \geq 0$. Let's note this by (**).

Now I can use (*) and (**) to prove that $f$ is convex. (*) and (**) => $f(y) \geq f(x) + \nabla f(x)^T(y-x)$ => $f$ is convex by the first order of convexity. Q.E.D. (The second direction is quite similar).

Now, my question is how to formally prove (*) and (**). I know it's follows from Taylor's theorem and Lagrange form of the reminder.

## 1 Answer

We can show that (*) holds using Taylor's theorem in one real variable (see here). We have that $$f(x)=f(a)+f'(a)(x-a)+\frac{f''(\xi_L)}{2!}(x-a)^2,$$ where $$\xi_L\in(a,x)$$. Set $$g(t)=f(x+t(y-x))$$. Then $$g(1)=g(0)+g'(0)+\frac{g''(\xi_L)}{2!},$$ where $$\xi_L\in(0,1)$$ (as you mentioned, this is the Lagrange form of the remainder). Since $$g'(a)=\nabla f(x)^{\mathrm T}(y-x) \quad\text{and}\quad g''(a)=(y-x)^{\mathrm T}\nabla^2f(x+a(y-x))(y-x),$$ we have that $$f(y)=f(x)+\nabla f(x)^{\mathrm T}(y-x)+(y-x)^{\mathrm T}\nabla^2f(x+a(y-x))(y-x)$$ with some $$a\in(0,1)$$, which establishes (*).

To prove (**), we only need to notice that this directly follows from the second-order condition. The second order condition is that the Hessian $$\nabla^2f(z)$$ is positive semidefinite, which means that $$v^{\mathrm T} \nabla^2f(z)v\ge0$$ for any $$z$$ in the domain of $$f$$ and for any vector $$v$$. Set $$z=x+a(y-x)$$ and $$v=y-x$$ to conclude.

I hope this helps.