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. A. Goldstein and J. F. Price,*An effective algorithm for minimization*, Numer. Math.**10**(1967), 184–189. MR**0217995**, https://doi.org/10.1007/BF02162162**[5]**H. Y. Huang,*Unified approach to quadratically convergent algorithms for function minimization*, J. Optimization Theory Appl.**5**(1970), 405–423. MR**0288939**, https://doi.org/10.1007/BF00927440**[6]**Garth P. McCormick and Klaus Ritter,*Methods of conjugate directions versus quasi-Newton methods*, Math. Programming**3**(1972), 101–116. MR**0302204**, https://doi.org/10.1007/BF01584978**[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.

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