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

DOI:
https://doi.org/10.1090/S0025-5718-1974-0343581-1

MathSciNet review:
0343581

Full-text PDF

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

*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 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 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.

**[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.

Retrieve articles in *Mathematics of Computation*
with MSC:
65H05

Retrieve articles in all journals with MSC: 65H05

Additional Information

DOI:
https://doi.org/10.1090/S0025-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