Local convergence theory of inexact Newton methods based on structured least change updates

Martínez, José Mario

doi:10.1090/S0025-5718-1990-1023050-5

Local convergence theory of inexact Newton methods based on structured least change updates
HTML articles powered by AMS MathViewer

by José Mario Martínez PDF

Math. Comp. 55 (1990), 143-167 Request permission

Abstract:

In this paper we introduce a local convergence theory for Least Change Secant Update methods. This theory includes most known methods of this class, as well as some new interesting quasi-Newton methods. Further, we prove that this class of LCSU updates may be used to generate iterative linear methods to solve the Newton linear equation in the Inexact-Newton context. Convergence at a q-superlinear rate (or at an "ideal" linear rate, in the sense of Dennis-Walker) of the Inexact Newton methods generated in this way is proved, independently of the number of iterations used in the linear iterative subalgorithm. We apply the new theory to some particular methods.

References

Least squares methods

C. G. Broyden, A class of methods for solving nonlinear simultaneous equations, Math. Comp. 19 (1965), 577–593. MR 198670, DOI 10.1090/S0025-5718-1965-0198670-6
C. G. Broyden, The convergence of an algorithm for solving sparse nonlinear systems, Math. Comp. 25 (1971), 285–294. MR 297122, DOI 10.1090/S0025-5718-1971-0297122-5
C. G. Broyden, J. E. Dennis Jr., and Jorge J. Moré, On the local and superlinear convergence of quasi-Newton methods, J. Inst. Math. Appl. 12 (1973), 223–245. MR 341853, DOI 10.1093/imamat/12.3.223

Sparse quasi-Newton methods and the continuation problem

Variable metric method for minimization

Ron S. Dembo, Stanley C. Eisenstat, and Trond Steihaug, Inexact Newton methods, SIAM J. Numer. Anal. 19 (1982), no. 2, 400–408. MR 650059, DOI 10.1137/0719025

An adaptive nonlinear least-squares algorithm

7

J. E. Dennis Jr. and Earl S. Marwil, Direct secant updates of matrix factorizations, Math. Comp. 38 (1982), no. 158, 459–474. MR 645663, DOI 10.1090/S0025-5718-1982-0645663-8
J. E. Dennis Jr. and Jorge J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp. 28 (1974), 549–560. MR 343581, DOI 10.1090/S0025-5718-1974-0343581-1
J. E. Dennis Jr. and Jorge J. Moré, Quasi-Newton methods, motivation and theory, SIAM Rev. 19 (1977), no. 1, 46–89. MR 445812, DOI 10.1137/1019005
J. E. Dennis Jr. and R. B. Schnabel, Least change secant updates for quasi-Newton methods, SIAM Rev. 21 (1979), no. 4, 443–459. MR 545880, DOI 10.1137/1021091
John E. Dennis Jr. and Robert B. Schnabel, Numerical methods for unconstrained optimization and nonlinear equations, Prentice Hall Series in Computational Mathematics, Prentice Hall, Inc., Englewood Cliffs, NJ, 1983. MR 702023
J. E. Dennis Jr. and Homer F. Walker, Convergence theorems for least-change secant update methods, SIAM J. Numer. Anal. 18 (1981), no. 6, 949–987. MR 638993, DOI 10.1137/0718067
I. S. Duff, A. M. Erisman, and J. K. Reid, Direct methods for sparse matrices, Monographs on Numerical Analysis, The Clarendon Press, Oxford University Press, New York, 1986. Oxford Science Publications. MR 892734
P. E. Gill, G. H. Golub, W. Murray, and M. A. Saunders, Methods for modifying matrix factorizations, Math. Comp. 28 (1974), 505–535. MR 343558, DOI 10.1090/S0025-5718-1974-0343558-6
Gene H. Golub and Charles F. Van Loan, Matrix computations, Johns Hopkins Series in the Mathematical Sciences, vol. 3, Johns Hopkins University Press, Baltimore, MD, 1983. MR 733103
Andreas Griewank, The local convergence of Broyden-like methods on Lipschitzian problems in Hilbert spaces, SIAM J. Numer. Anal. 24 (1987), no. 3, 684–705. MR 888756, DOI 10.1137/0724045
A. Griewank and Ph. L. Toint, On the unconstrained optimization of partially separable functions, Nonlinear optimization, 1981 (Cambridge, 1981) NATO Conf. Ser. II: Systems Sci., Academic Press, London, 1982, pp. 301–312. MR 775354
A. Griewank and Ph. L. Toint, Partitioned variable metric updates for large structured optimization problems, Numer. Math. 39 (1982), no. 1, 119–137. MR 664541, DOI 10.1007/BF01399316
A. Griewank and Ph. L. Toint, Local convergence analysis for partitioned quasi-Newton updates, Numer. Math. 39 (1982), no. 3, 429–448. MR 678746, DOI 10.1007/BF01407874
A. Griewank and Ph. L. Toint, Numerical experiments with partially separable optimization problems, Numerical analysis (Dundee, 1983) Lecture Notes in Math., vol. 1066, Springer, Berlin, 1984, pp. 203–220. MR 760465, DOI 10.1007/BFb0099526
Magnus R. Hestenes and Eduard Stiefel, Methods of conjugate gradients for solving linear systems, J. Research Nat. Bur. Standards 49 (1952), 409–436 (1953). MR 0060307, DOI 10.6028/jres.049.044
George W. Johnson and Nieves H. Austria, A quasi-Newton method employing direct secant updates of matrix factorizations, SIAM J. Numer. Anal. 20 (1983), no. 2, 315–325. MR 694521, DOI 10.1137/0720021
C. T. Kelley and E. W. Sachs, Broyden’s method for approximate solution of nonlinear integral equations, J. Integral Equations 9 (1985), no. 1, 25–43. MR 793102
Kenneth Levenberg, A method for the solution of certain non-linear problems in least squares, Quart. Appl. Math. 2 (1944), 164–168. MR 10666, DOI 10.1090/S0033-569X-1944-10666-0

Linear and nonlinear programming

Donald W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, J. Soc. Indust. Appl. Math. 11 (1963), 431–441. MR 153071, DOI 10.1137/0111030
J. M. Martínez, A quasi-Newton method with a new updating for the $LDU$ factorization of the approximate Jacobian, Mat. Apl. Comput. 2 (1983), no. 2, 131–141 (English, with Portuguese summary). MR 865227
J. M. Martínez, Quasi-Newton methods with factorization scaling for solving sparse nonlinear systems of equations, Computing 38 (1987), no. 2, 133–141 (English, with German summary). MR 889958, DOI 10.1007/BF02240178

A family of Quasi-Newton methods with direct secant updates of matrix factorizations

Exploiting sparsity in Newton-type methods

Earl Marwil, Convergence results for Schubert’s method for solving sparse nonlinear equations, SIAM J. Numer. Anal. 16 (1979), no. 4, 588–604. MR 537273, DOI 10.1137/0716044
J. J. Moré and J. A. Trangenstein, On the global convergence of Broyden’s method, Math. Comp. 30 (1976), no. 135, 523–540. MR 418451, DOI 10.1090/S0025-5718-1976-0418451-2
J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
Ole Østerby and Zahari Zlatev, Direct methods for sparse matrices, Lecture Notes in Computer Science, vol. 157, Springer-Verlag, Berlin, 1983. MR 716136, DOI 10.1007/3-540-12676-7
M. J. D. Powell, A new algorithm for unconstrained optimization, Nonlinear Programming (Proc. Sympos., Univ. of Wisconsin, Madison, Wis., 1970) Academic Press, New York, 1970, pp. 31–65. MR 0272162
Ekkehard W. Sachs, Broyden’s method in Hilbert space, Math. Programming 35 (1986), no. 1, 71–82. MR 842635, DOI 10.1007/BF01589442
L. K. Schubert, Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27–30. MR 258276, DOI 10.1090/S0025-5718-1970-0258276-9
Hubert Schwetlick, Numerische Lösung nichtlinearer Gleichungen, Mathematik für Naturwissenschaft und Technik [Mathematics for Science and Technology], vol. 17, VEB Deutscher Verlag der Wissenschaften, Berlin, 1979 (German). MR 519682
Ph. L. Toint, On sparse and symmetric matrix updating subject to a linear equation, Math. Comp. 31 (1977), no. 140, 954–961. MR 455338, DOI 10.1090/S0025-5718-1977-0455338-4
Ph. L. Toint, Some numerical results using a sparse matrix updating formula in unconstrained optimization, Math. Comp. 32 (1978), no. 143, 839–851. MR 483452, DOI 10.1090/S0025-5718-1978-0483452-7
Ph. L. Toint, Numerical solution of large sets of algebraic nonlinear equations, Math. Comp. 46 (1986), no. 173, 175–189. MR 815839, DOI 10.1090/S0025-5718-1986-0815839-9