Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Mathematics of Computation
Mathematics of Computation
ISSN 1088-6842(online) ISSN 0025-5718(print)

 

A characterization of superlinear convergence and its application to quasi-Newton methods


Authors: J. E. Dennis and Jorge J. Moré
Journal: Math. Comp. 28 (1974), 549-560
MSC: Primary 65H05
MathSciNet review: 0343581
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Let F be a mapping from real n-dimensional Euclidean space into itself. Most practical algorithms for finding a zero of F are of the form

$\displaystyle {x_{k + 1}} = {x_k} - B_k^{ - 1}F{x_k},$

where $ \{ {B_k}\} $ is a sequence of nonsingular matrices. The main result of this paper is a characterization theorem for the superlinear convergence to a zero of F of sequences of the above form. This result is then used to give a unified treatment of the results on the superlinear convergence of the Davidon-Fletcher-Powell method obtained by Powell for the case in which exact line searches are used, and by Broyden, Dennis, and Moré for the case without line searches. As a by-product, several results on the asymptotic behavior of the sequence $ \{ {B_k}\} $ are obtained.

An interesting aspect of these results is that superlinear convergence is obtained without any consistency conditions; i.e., without requiring that the sequence $ \{ {B_k}\} $ converge to the Jacobian matrix of F at the zero. In fact, a modification of an example due to Powell shows that most of the known quasi-Newton methods are not, in general, consistent. Finally, it is pointed out that the above-mentioned characterization theorem applies to other single and double rank quasi-Newton methods, and that the results of this paper can be used to obtain their superlinear convergence.


References [Enhancements On Off] (What's this?)

  • [1] K. M. Brown & J. E. Dennis, Jr., "A new algorithm for nonlinear least-squares curve fitting," in Mathematical Software, John R. Rice, Editor, Academic Press, New York, 1971, pp. 391-396.
  • [2] C. G. Broyden, J. E. Dennis & J. J. Moré, On the Local and Superlinear Convergence of Quasi-Newton Methods, Cornell Computer Science Technical Report 72-137, 1972; J. Inst. Math. Appl. (To appear.)
  • [3] R. Fletcher, "A new approach to variable metric algorithms," Comput. J., v. 13, 1970, pp. 317-322.
  • [4] A. Goldstein & J. Price, "An effective algorithm for minimization," Numer. Math., v. 10, 1967, pp. 184-189. MR 36 #1084. MR 0217995 (36:1084)
  • [5] H. Y. Huang, "Unified approach to quadratically convergent algorithms for function minimization." J. Optimization Theory Appl., v. 5, 1970, pp. 405-423. MR 44 #6134. MR 0288939 (44:6134)
  • [6] G. McCormick & K. Ritter, "Methods of conjugate directions versus quasi-Newton methods," Math. Programming, v. 3, 1972, pp. 101-116. MR 46 #1357. MR 0302204 (46:1357)
  • [7] J. M. Ortega & W. C. Rheinboldt, Iterative Solution of Nonlinear Equations in Several Variables, Academic Press, New York, 1970. MR 42 #8686. MR 0273810 (42:8686)
  • [8] M. J. D. Powell, "On the convergence of the variable metric algorithm," J. Inst. Math. Appl., v. 7, 1971, pp. 21-36. MR 43 #5698. MR 0279977 (43:5698)
  • [9] M. J. D. Powell, Private communication, 1972.
  • [10] K. Ritter, "Superlinearly convergent methods for unconstrained minimization problems," Proc. ACM, Boston, 1972, pp. 1137-1145.
  • [11] R. Voigt, Rates of Convergence for Iterative Methods for Nonlinear Systems of Equations, Ph.D. Thesis, University of Maryland, College Park, Md., 1969.

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65H05

Retrieve articles in all journals with MSC: 65H05


Additional Information

DOI: http://dx.doi.org/10.1090/S0025-5718-1974-0343581-1
PII: S 0025-5718(1974)0343581-1
Keywords: Quasi-Newton methods, variable metric methods, superlinear convergence, iterative methods for nonlinear equations
Article copyright: © Copyright 1974 American Mathematical Society