2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.