A characterization of superlinear convergence and its application to quasiNewton methods
Authors:
J. E. Dennis and Jorge J. Moré
Journal:
Math. Comp. 28 (1974), 549560
MSC:
Primary 65H05
DOI:
https://doi.org/10.1090/S00255718197403435811
MathSciNet review:
0343581
Fulltext PDF Free Access
Abstract  References  Similar Articles  Additional Information
Abstract: Let F be a mapping from real ndimensional Euclidean space into itself. Most practical algorithms for finding a zero of F are of the form \[ {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 DavidonFletcherPowell 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 byproduct, 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 quasiNewton methods are not, in general, consistent. Finally, it is pointed out that the abovementioned characterization theorem applies to other single and double rank quasiNewton methods, and that the results of this paper can be used to obtain their superlinear convergence.

K. M. Brown & J. E. Dennis, Jr., "A new algorithm for nonlinear leastsquares curve fitting," in Mathematical Software, John R. Rice, Editor, Academic Press, New York, 1971, pp. 391396.
C. G. Broyden, J. E. Dennis & J. J. Moré, On the Local and Superlinear Convergence of QuasiNewton Methods, Cornell Computer Science Technical Report 72137, 1972; J. Inst. Math. Appl. (To appear.)
R. Fletcher, "A new approach to variable metric algorithms," Comput. J., v. 13, 1970, pp. 317322.
 A. A. Goldstein and J. F. Price, An effective algorithm for minimization, Numer. Math. 10 (1967), 184–189. MR 217995, DOI https://doi.org/10.1007/BF02162162
 H. Y. Huang, Unified approach to quadratically convergent algorithms for function minimization, J. Optim. Theory Appl. 5 (1970), 405–423. MR 288939, DOI https://doi.org/10.1007/BF00927440
 Garth P. McCormick and Klaus Ritter, Methods of conjugate directions versus quasiNewton methods, Math. Programming 3 (1972), 101–116. MR 302204, DOI https://doi.org/10.1007/BF01584978
 J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New YorkLondon, 1970. MR 0273810
 M. J. D. Powell, On the convergence of the variable metric algorithm, J. Inst. Math. Appl. 7 (1971), 21–36. MR 279977 M. J. D. Powell, Private communication, 1972. K. Ritter, "Superlinearly convergent methods for unconstrained minimization problems," Proc. ACM, Boston, 1972, pp. 11371145. 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
Keywords:
QuasiNewton methods,
variable metric methods,
superlinear convergence,
iterative methods for nonlinear equations
Article copyright:
© Copyright 1974
American Mathematical Society