A characterization of superlinear convergence and its application to quasiNewton methods
HTML articles powered by AMS MathViewer
 by J. E. Dennis and Jorge J. Moré PDF
 Math. Comp. 28 (1974), 549560 Request permission
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.References

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 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 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 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.
Additional Information
 © Copyright 1974 American Mathematical Society
 Journal: Math. Comp. 28 (1974), 549560
 MSC: Primary 65H05
 DOI: https://doi.org/10.1090/S00255718197403435811
 MathSciNet review: 0343581