Remote Access Mathematics of Computation
Green Open Access

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. A. Goldstein and J. F. Price, An effective algorithm for minimization, Numer. Math. 10 (1967), 184–189. MR 0217995
  • [5] H. Y. Huang, Unified approach to quadratically convergent algorithms for function minimization, J. Optimization Theory Appl. 5 (1970), 405–423. MR 0288939
  • [6] Garth P. McCormick and Klaus Ritter, Methods of conjugate directions versus quasi-Newton methods, Math. Programming 3 (1972), 101–116. MR 0302204
  • [7] J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
  • [8] M. J. D. Powell, On the convergence of the variable metric algorithm, J. Inst. Math. Appl. 7 (1971), 21–36. MR 0279977
  • [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

Keywords: Quasi-Newton methods, variable metric methods, superlinear convergence, iterative methods for nonlinear equations
Article copyright: © Copyright 1974 American Mathematical Society