Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose that we are trying to minimize a function $f$ on $\mathbb{R}^n$ and we apply Newton's method, updating: \begin{align} \mathbf{x}_{n+1} = \mathbf{x}_n - [\nabla^2 f(\mathbf{x}_n)]^{-1} \nabla f(\mathbf{x}_n). \end{align} If the Hessian $\nabla^2 f$ is not positive semidefinite, Newton's method may update $x$ against the gradient because \begin{align} \mathbf{x}_{n+1} - \mathbf{x}_n &= - [\nabla^2 f(\mathbf{x}_n)]^{-1} \nabla f(\mathbf{x}_n) \\ \implies \nabla f(\mathbf{x}_n)^T(\mathbf{x}_{n+1} - \mathbf{x}_n) &= - \nabla f(\mathbf{x}_n)^T[\nabla^2 f(\mathbf{x}_n)]^{-1} \nabla f(\mathbf{x}_n) \end{align} could have either sign. Is there a graphical way to interpret what's going on?

share|improve this question
add comment

1 Answer 1

up vote 1 down vote accepted

You say you're trying to minimize, but Newton's method actually looks for a critical point (a solution of $\nabla f(x) = 0$). A critical point $x_0$ where the Hessian matrix is not positive semidefinite is not a local minimum but a saddle point or a local maximum: if $v$ is an eigenvector of $\nabla^2 f(x_0)$ for a negative eigenvalue $\lambda$ then $f(x_0 + t v) = f(x_0) + \lambda t^2 |v|^2/2 + O(|t|^3)$ as $t \to 0$.

share|improve this answer
    
Thanks for taking the time to answer. You're right that Newton's method will only give a local minimum (and will stop at a local maximum) since it's looking for a point where the gradient is zero. I am still having trouble visualizing the second part of your answer. –  Neil G Mar 21 '13 at 0:45
    
For the purposes of visualization, it may be helpful to consider a case where the Hessian matrix is diagonal. –  Robert Israel Mar 21 '13 at 1:22
    
Thanks, I think I see it now. Essentially, Newton's method is looking for points with zero slope, and decides for each eigenvector whether to go towards a local maximum or minimum based on the sign of the eigenvalue. Is that right? –  Neil G Mar 21 '13 at 4:55
    
If you're close enough to a critical point it will go to that critical point, whether it's a local max, local min, or saddle. –  Robert Israel Mar 21 '13 at 7:08
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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