Quasi-Newton Methods, Motivation and Theory

Quasi-Newton Methods, Motivation and Theory

November 1974 | J.E. Dennis and J.J. More
This paper motivates and justifies quasi-Newton methods as useful modifications of Newton's method for solving nonlinear systems of equations and unconstrained minimization problems. It provides an overview of important theoretical results and discusses the derivation and relationship between various quasi-Newton methods. The paper also includes a survey of theoretical results that explain the behavior of quasi-Newton methods and provides background material in Sections 2 and 6 to motivate these methods. The paper shows that all known practical quasi-Newton methods can be derived from natural considerations, and that the relationship between these methods is clear. It also contains a survey of theoretical results that yield insight into the behavior of quasi-Newton methods. The paper discusses the derivation of various quasi-Newton updates by considering them as methods for generating approximations to derivatives, such as Jacobians in nonlinear equations and Hessians in unconstrained minimization. This perspective suggests how to use quasi-Newton methods in other areas such as least squares and constrained optimization. Theoretical results show that there are four quasi-Newton updates that are globally and superlinearly convergent for linear problems and locally and superlinearly convergent for nonlinear problems. These updates are Broyden's 1965 update for nonlinear equations, Powell's symmetric form of Broyden's update, the Davidon-Fletcher-Powell update, and the Broyden-Fletcher-Goldfarb-Shanno update. The theoretical results tend to explain why these four updates are the ones most used in practical work. The paper also includes rate of convergence results, emphasizing superlinear convergence and its geometric interpretation. It discusses the importance of understanding the rate of convergence of different algorithms, as it is as important as the fact that the algorithm converges. The paper also discusses the derivation of Broyden's method, which is a method for approximating Jacobian matrices. It shows how Broyden's method reduces the computational cost of Newton's method by avoiding the need to compute the Jacobian matrix at each iteration. The paper also discusses the local convergence results of Broyden's method and shows that it is locally and superlinearly convergent at the solution. The paper concludes with a discussion of the global and superlinear convergence of Broyden's method for linear problems.This paper motivates and justifies quasi-Newton methods as useful modifications of Newton's method for solving nonlinear systems of equations and unconstrained minimization problems. It provides an overview of important theoretical results and discusses the derivation and relationship between various quasi-Newton methods. The paper also includes a survey of theoretical results that explain the behavior of quasi-Newton methods and provides background material in Sections 2 and 6 to motivate these methods. The paper shows that all known practical quasi-Newton methods can be derived from natural considerations, and that the relationship between these methods is clear. It also contains a survey of theoretical results that yield insight into the behavior of quasi-Newton methods. The paper discusses the derivation of various quasi-Newton updates by considering them as methods for generating approximations to derivatives, such as Jacobians in nonlinear equations and Hessians in unconstrained minimization. This perspective suggests how to use quasi-Newton methods in other areas such as least squares and constrained optimization. Theoretical results show that there are four quasi-Newton updates that are globally and superlinearly convergent for linear problems and locally and superlinearly convergent for nonlinear problems. These updates are Broyden's 1965 update for nonlinear equations, Powell's symmetric form of Broyden's update, the Davidon-Fletcher-Powell update, and the Broyden-Fletcher-Goldfarb-Shanno update. The theoretical results tend to explain why these four updates are the ones most used in practical work. The paper also includes rate of convergence results, emphasizing superlinear convergence and its geometric interpretation. It discusses the importance of understanding the rate of convergence of different algorithms, as it is as important as the fact that the algorithm converges. The paper also discusses the derivation of Broyden's method, which is a method for approximating Jacobian matrices. It shows how Broyden's method reduces the computational cost of Newton's method by avoiding the need to compute the Jacobian matrix at each iteration. The paper also discusses the local convergence results of Broyden's method and shows that it is locally and superlinearly convergent at the solution. The paper concludes with a discussion of the global and superlinear convergence of Broyden's method for linear problems.
Reach us at info@study.space
[slides and audio] Quasi-Newton Methods%2C Motivation and Theory