Quasi-Newton method

From Wikipedia, the free encyclopedia

In optimization, quasi-Newton methods are well-known algorithms for finding local maxima and minima of functions. Quasi-Newton methods are based on Newton's method, but they approximate the inverse Hessian matrix in order to reduce the amount of computation per iteration.

The first quasi-Newton algorithm was proposed by W.C. Davidon, a physicist working at Argonne National Laboratory. Like the story of QuickSort, Davidon got the trouble of applying optimization algorithms on his research, thus he decided to improve such algorithm. Eventually he developed the first quasi-Newton algorithm in the mid 1950s.

The most popular quasi-Newton algorithms are DFP algorithm and BFGS method. The former was developed by Davidon in 1959 and was subsequently modified by Fletcher and Powell in 1963; the later was suggested independently by Broyden, Fletcher, Goldfarb, and Shanno, in 1970.

[edit] References

• Eventually W.C. Davidon's paper published. William C. Davidon, Variable Metric Method for Minimization, SIOPT Volume 1 Issue 1, Pages 1-17, 1991.
• Nocedal, Jorge & Wright, Stephen J. (1999). Numerical Optimization. Springer-Verlag. ISBN 0-387-98793-2.
• Edwin K.P.Chong and Stanislaw H.Zak, An Introduction to Optimization 2ed, John Wiley & Sons Pte. Ltd. August 2001.