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
-
Å. Björck, Least squares methods, Handbook of Numerical Analysis, vol 1 (P. G. Ciarlet and J. L. Lions, eds.), Elsevier, North-Holland, 1987.
- 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 F. F. Chadee, Sparse quasi-Newton methods and the continuation problem, T. R. SOL 85-8, Dept. of Operations Research, Stanford University, Stanford, CA, 1985. W. C. Davidon, Variable metric method for minimization, Report ANL-5990 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 least-squares algorithm, ACM Trans. Math. Software 7 (1981), 348-368.
- 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 D. G. Luenberger, Linear and nonlinear programming, 2nd ed., Addison-Wesley, Reading, Mass., 1984.
- 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, SIAM J. Numer. Anal. (to appear). E. S. Marwil, Exploiting sparsity in Newton-type 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/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
Additional Information
- © Copyright 1990 American Mathematical Society
- Journal: Math. Comp. 55 (1990), 143-167
- MSC: Primary 65H10; Secondary 90C30
- DOI: https://doi.org/10.1090/S0025-5718-1990-1023050-5
- MathSciNet review: 1023050