4
$\begingroup$

I am reading "Deep Learning" by Ian Goodfellow. At page 86, the author explains how to use the Hessian to evaluate whether a point of a multivariate function is a maximum or a minimum

At a critical point, where $ \nabla_x f(x)=0 $, we can examine the eigenvalues of the Hessian to determine whether the critical point is a local maximum, local minimum or saddle point. When the Hessian is positive definite (all its eigenvalues are positive), the point is a local minimum. [...] Likewise when the Hessian is negative (all its eigenvalues are negative), the point is a local maximum. In multiple dimensions, it is actually possible to find positive evidence of saddle points in some cases. When at least one eigenvalue is positive and at least one eigenvalue is negative, we know that $x$ is a local maximum on one cross section of $f$ but a local minimum on another cross-section. [...] The test is inconclusive whenever all the nonzero eigenvalues have the same sign but at least one eigenvalue is zero. This is because the univariate second derivative test is inconclusive in the cross section corresponding to the zero eigenvalue

So far so good. At page 89 it talks about convex optimization, and says that:

Convex functions - functions for which the Hessian is positive semi-definite everywhere [..] are well-behaved because they lack saddle points

But if the Hessian is positive-semidefinite, it means that some eigenvalues may be zero, while the others are positive. I thought that "whenever all the nonzero eigenvalues have the same sign but at least one eigenvalue is zero" the test was inconclusive. So why does it says that they surely lack saddle points?

$\endgroup$
1
$\begingroup$

Saddle points ensure the function is not convex near that point. For example $0$ is a saddle point of the function $f(x)=x^3$ and it is not a convex function even if we restrict the domain to some small ball around zero. So by assuming the function is convex, you've tacitly assumed there are no saddle points.

$\endgroup$
0
1
$\begingroup$

The test for convexity in the first part, refers to the hessian at a single value $a$ for which $\nabla_x f(x)|_{x=a} = 0$. The condition for convexity you've quoted is with respect to all points in the domain.

So basically, you can compute the hessian at a critical point and if it has a 0 eigenvalue with the rest positive, the test is inconclusive. If you compute the hessian not just at the critical point, but at every point and find it's positive semidefinite, then the function is convex.

For $f(x) = x^3$, the 'Hessian' at the critical point $0$ is $H(0) =0$ so we can't know if the value is a minimum (indeed it is not). However, the hessian for an arbitrary value $a$ is $H(a) = 6a$. The function is not convex because, for example, the hessian at $-1$ is $H(-1) = -6$.

For $f(x) = x^4$, the Hessian at the critical point $0$ is $H(0)=0$, so the test is inconclusive as to whether this is a minimum. However, the hessian for arbitrary $a$ is $H(a) = 12a^2$ so we can be sure the function is convex at the the critical point is actually a minimum.

$\endgroup$
1
$\begingroup$

One property of a differentiable convex function $f:\mathbb R^n \to \mathbb R$ is that if $a \in \mathbb R^n$ then $$ f(x) \geq f(a) + \langle \nabla f(a), x-a\rangle $$ for all $x \in \mathbb R^n$. It follows that if $\nabla f(a) = 0$ then $a$ is a global minimizer of $f$.

$\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.