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
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 where 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 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 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.
 [1]
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.
 [2]
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.)
 [3]
R. Fletcher, "A new approach to variable metric algorithms," Comput. J., v. 13, 1970, pp. 317322.
 [4]
A. Goldstein & J. Price, "An effective algorithm for minimization," Numer. Math., v. 10, 1967, pp. 184189. 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. 405423. MR 44 #6134. MR 0288939 (44:6134)
 [6]
G. McCormick & K. Ritter, "Methods of conjugate directions versus quasiNewton methods," Math. Programming, v. 3, 1972, pp. 101116. 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. 2136. 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. 11371145.
 [11]
R. Voigt, Rates of Convergence for Iterative Methods for Nonlinear Systems of Equations, Ph.D. Thesis, University of Maryland, College Park, Md., 1969.
 [1]
 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.
 [2]
 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.)
 [3]
 R. Fletcher, "A new approach to variable metric algorithms," Comput. J., v. 13, 1970, pp. 317322.
 [4]
 A. Goldstein & J. Price, "An effective algorithm for minimization," Numer. Math., v. 10, 1967, pp. 184189. 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. 405423. MR 44 #6134. MR 0288939 (44:6134)
 [6]
 G. McCormick & K. Ritter, "Methods of conjugate directions versus quasiNewton methods," Math. Programming, v. 3, 1972, pp. 101116. 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. 2136. 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. 11371145.
 [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/S00255718197403435811
PII:
S 00255718(1974)03435811
Keywords:
QuasiNewton methods,
variable metric methods,
superlinear convergence,
iterative methods for nonlinear equations
Article copyright:
© Copyright 1974
American Mathematical Society
