Abstract
Quasi-Newton equations play a central role in quasi-Newton methods for optimization and various quasi-Newton equations are available. This paper gives a survey on these quasi-Newton equations and studies properties of quasi-Newton methods with updates satisfying different quasi-Newton equations. These include single-step quasi-Newton equations that use only gradient information and that use both gradient and function value information in one step, and multi-step quasi-Newton equations that use the gradient information in last m steps. Main properties of quasi-Newton methods with updates satisfying different quasi-Newton equations are studied. These properties include the finite termination property, invariance, heredity of positive definite updates, consistency of search directions, global convergence and local superlinear convergence properties.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
M.F. Anjos, A modified Broyden update with interpolation, SIAM Journal on Scientific Computing 14 (1993) 1359–1367.
C.G. Broyden, J.E. Dennis, Jr. and J.J. Moré, On the local and superlinear convergence of quasi-Newton methods, Journal of IMA 12 (1973) 223–245.
R.H. Byrd and J. Nocedal, A tool for the analysis of quasi-Newton methods with application to unconstrained minimization, SIAM Journal on Numerical Analysis 26 (1989) 727–739.
R.H. Byrd, J. Nocedal and Y. Yuan, Global convergence of a class of quasi-Newton methods on convex problems, SIAM Journal on Numerical Analysis 24 (1987) 1171–1190.
W.C. Davidon, Variable metric method for minimization, AEC Res. and Dev. Report ANL-5990 (1959).
W.C. Davidon, Optimally conditioned optimization algorithms without line searches, Mathematical Programming 9 (1975) 1–30.
W.C. Davidon, Conic approximations and collinear scalings for optimizer, SIAM Journal on Numerical Analysis 17 (1980) 268–281.
J.E. Dennis and J.J. Moré, A characterization of superliner convergence and its application to quasi-Newton methods, Mathematics of Computation 28 (1974) 549–560.
J.E. Dennis and J.J. Moré, Quasi-Newton methods, motivation and theory, SIAM Review 19 (1977) 46–89.
L.C.W. Dixon, Quasi-Newton algorithms generate identical points, Mathematical Programing 2 (1972) 383–387.
R. Fletcher, Practical Methods of Optimization, Vol. 1, Unconstrained Optimization (Wiley, New York, 1980).
R. Fletcher and M.J.D. Powell, A rapidly convergent descent method for minimization, Computer Journal 6 (1963) 163–168.
J.A. Ford and I.A. Moghrabi, Alternative parameter choices for multi-step quasi-Newton methods, Optimization Methods and Software 2 (1993) 357–370.
J.A. Ford and I.A. Moghrabi, Multi-step quasi-Newton methods for optimization, Journal of Computational and Applied Mathematics 50 (1994) 305–323.
H.Y. Huang, Unified approach to quadratically convergent algorithms for function minimization, Journal of Optimization Theory and Applications 5 (1970) 405–423.
W.D. Lin and C.X. Xu, Global convergence properties of convex Broyden family of modified quasi-Newton methods based on the new quasi-Newton equations, Presented at International Conference on Nonlinear Programming and Variational Inequalities, Hong Kong (15-18 December 1998).
M.J.D. Powell, On the convergence of the variable metric algorithm, Journal of IMA 7 (1971) 21–36.
M.J.D. Powell, Some properties of the variable metric algorithm, in: Numerical Methods for Nonlinear Optimization, ed. F.A. Lootsman (Academic Press, London, 1972).
M.J.D. Powell, Some global convergence properties of a variable metric algorithm for minimization without exact line searches, in: Nonlinear Programming, SIAM-AMS Proceedings, Vol. IX, eds. R.W. Cotte and C.E. Lemke (SIAM, Philadephia, 1976).
E. Spedicato, A class of rank-one positive definite quasi-Newton updates for unconstrained optimization, Math. Operationsforsch. Stat. Ser. A, Optimization 14 (1983) 61–70.
J.H. Wilkinson, The Algebraic Eigenvalue Problem (Oxford University Press, Oxford, 1965).
Y. Yuan, A modified BFGS algorithm for unconstrained optimization, IMA Journal of Numerical Analysis 11 (1991) 325–332.
J.Z. Zhang, N.Y. Deng and L.H. Chen, A new quasi-Newton equation and related methods for unconstrained optimization, Journal of Optimization Theory and Applications 102 (1999) 147–167.
J.Z. Zhang and C.X. Xu, Properties and numerical performance of quasi-Newton methods with modified quasi-Newton equations, Journal of Computational and Applied Mathematics, to appear.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Xu, C., Zhang, J. A Survey of Quasi-Newton Equations and Quasi-Newton Methods for Optimization. Annals of Operations Research 103, 213–234 (2001). https://doi.org/10.1023/A:1012959223138
Issue Date:
DOI: https://doi.org/10.1023/A:1012959223138