Welcome to the MedLibrary.org Wikipedia Supplement on Newton's method in optimization -- Please Click to Return to Front Page

A comparison of gradient descent (green) and Newton's method (red) for minimizing a function (with small step sizes). Newton's method uses curvature information to take a more direct route.

In mathematics, Newton's method is a well-known algorithm for finding roots of equations in one or more dimensions. It can also be used to find local maxima and local minima of functions by noticing that if a real number x * is a stationary point of a function f(x), then x * is a root of the derivative f'(x), and therefore one can solve for x * by applying Newton's method to f'(x). The Taylor expansion of f(x)

,

attains its extremum when Δx solves the linear equation:

and is positive. Thus, provided that is a twice-differentiable function and the initial guess is chosen close enough to x * , the sequence (x_n) defined by

will converge towards x * .

This iterative scheme can be generalized to several dimensions by replacing the derivative with the gradient, , and the reciprocal of the second derivative with the inverse of the Hessian matrix, . One obtains the iterative scheme

Usually Newton's method is modified to include a small step size γ > 0 instead of γ = 1

This is often done to ensure that the Wolfe conditions are satisfied at each step of the iteration.

The geometric interpretation of Newton's method is that at each iteration one approximates by a quadratic function around , and then takes a step towards the maximum/minimum of that quadratic function. (If happens to be a quadratic function, then the exact extremum is found in one step.)

Newton's method converges much faster towards a local maximum or minimum than gradient descent. In fact, every local minimum has a neighborhood N such that, if we start with Newton's method with step size γ = 1 converges quadratically (if the Hessian is invertible in that neighborhood).

Finding the inverse of the Hessian is an expensive operation, so the linear equation

.

is often solved approximately (but to great accuracy) using a method such as conjugate gradient. There also exist various quasi-Newton methods, where an approximation for the Hessian is used instead.

If the Hessian is close to a non-invertible matrix, the inverted Hessian can be numerically unstable and the solution may diverge. In this case, certain workarounds have been tried in the past, which have varied success with certain problems. One can, for example, modify the Hessian by adding a correction matrix B_n so as to make positive definite. One approach is to diagonalize H_f and choose B_n so that has the same eigenvectors as H_f, but with each negative eigenvalue replaced by ε > 0.

See also

• Gradient descent
• Gauss–Newton algorithm
• Levenberg–Marquardt algorithm
• Optimization

References

• Avriel, Mordecai (2003). Nonlinear Programming: Analysis and Methods. Dover Publishing. ISBN 0-486-43227-0.
• Nocedal, Jorge & Wright, Stephen J. (1999). Numerical Optimization. Springer-Verlag. ISBN 0-387-98793-2.

External links

• MIT video lecture about Newton's Method

Wikipedia content modification information:

• This page was last modified on 8 August 2008, at 12:48.

Wikipedia Authorship and Review

Wikipedia content provided here is not reviewed directly by MedLibrary.org. Wikipedia content is authored by an open community of volunteers and is not produced by or in any way affiliated with MedLibrary.org.

Wikipedia Usage Guidelines

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article on "Newton's method in optimization".

The URL for this specific entry is:

• http://medlibrary.org/medwiki/Newton's_method_in_optimization

All Wikipedia text is available under the terms of the GNU Free Documentation License. (See Copyrights for details). Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc.