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), 143167 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 quasiNewton 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 InexactNewton context. Convergence at a qsuperlinear rate (or at an "ideal" linear rate, in the sense of DennisWalker) 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

Å. Björck, Least squares methods, Handbook of Numerical Analysis, vol 1 (P. G. Ciarlet and J. L. Lions, eds.), Elsevier, NorthHolland, 1987.
 C. G. Broyden, A class of methods for solving nonlinear simultaneous equations, Math. Comp. 19 (1965), 577–593. MR 198670, DOI 10.1090/S00255718196501986706
 C. G. Broyden, The convergence of an algorithm for solving sparse nonlinear systems, Math. Comp. 25 (1971), 285–294. MR 297122, DOI 10.1090/S00255718197102971225
 C. G. Broyden, J. E. Dennis Jr., and Jorge J. Moré, On the local and superlinear convergence of quasiNewton methods, J. Inst. Math. Appl. 12 (1973), 223–245. MR 341853, DOI 10.1093/imamat/12.3.223 F. F. Chadee, Sparse quasiNewton methods and the continuation problem, T. R. SOL 858, Dept. of Operations Research, Stanford University, Stanford, CA, 1985. W. C. Davidon, Variable metric method for minimization, Report ANL5990 Rev (1959), Argonne National Laboratory, Argonne, Ill., 1959.
 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 J. E. Dennis, Jr., D. M. Gay, and R. E. Welsch, An adaptive nonlinear leastsquares algorithm, ACM Trans. Math. Software 7 (1981), 348368.
 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/S00255718198206456638
 J. E. Dennis Jr. and Jorge J. Moré, A characterization of superlinear convergence and its application to quasiNewton methods, Math. Comp. 28 (1974), 549–560. MR 343581, DOI 10.1090/S00255718197403435811
 J. E. Dennis Jr. and Jorge J. Moré, QuasiNewton 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 quasiNewton 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 leastchange 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/S00255718197403435586
 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 Broydenlike 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 quasiNewton 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 quasiNewton 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 nonlinear problems in least squares, Quart. Appl. Math. 2 (1944), 164–168. MR 10666, DOI 10.1090/S0033569X1944106660 D. G. Luenberger, Linear and nonlinear programming, 2nd ed., AddisonWesley, Reading, Mass., 1984.
 Donald W. Marquardt, An algorithm for leastsquares estimation of nonlinear parameters, J. Soc. Indust. Appl. Math. 11 (1963), 431–441. MR 153071, DOI 10.1137/0111030
 J. M. Martínez, A quasiNewton 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, QuasiNewton 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 QuasiNewton methods with direct secant updates of matrix factorizations, SIAM J. Numer. Anal. (to appear). E. S. Marwil, Exploiting sparsity in Newtontype methods, Cornell Applied Mathematics Ph.D. thesis, 1978.
 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/S00255718197604184512
 J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New YorkLondon, 1970. MR 0273810
 Ole Østerby and Zahari Zlatev, Direct methods for sparse matrices, Lecture Notes in Computer Science, vol. 157, SpringerVerlag, Berlin, 1983. MR 716136, DOI 10.1007/3540126767
 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 quasiNewton method for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27–30. MR 258276, DOI 10.1090/S00255718197002582769
 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/S00255718197704553384
 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/S00255718197804834527
 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/S00255718198608158399
Additional Information
 © Copyright 1990 American Mathematical Society
 Journal: Math. Comp. 55 (1990), 143167
 MSC: Primary 65H10; Secondary 90C30
 DOI: https://doi.org/10.1090/S00255718199010230505
 MathSciNet review: 1023050