Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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


Author: José Mario Martínez
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
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] Å. Björck, Least squares methods, Handbook of Numerical Analysis, vol 1 (P. G. Ciarlet and J. L. Lions, eds.), Elsevier, North-Holland, 1987.
  • [2] C. G. Broyden, A class of methods for solving nonlinear simultaneous equations, Math. Comp. 19 (1965), 577-593. MR 0198670 (33:6825)
  • [3] -, The convergence of an algorithm for solving sparse nonlinear systems, Math. Comp. 25 (1971), 285-294. MR 0297122 (45:6180)
  • [4] C. G. Broyden, J. E. Dennis, and J. J. Moré, On the local and superlinear convergence of quasi-Newton methods, J. Inst. Math. Appl. 12 (1973), 223-245. MR 0341853 (49:6599)
  • [5] 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.
  • [6] W. C. Davidon, Variable metric method for minimization, Report ANL-5990 Rev (1959), Argonne National Laboratory, Argonne, Ill., 1959.
  • [7] R. S. Dembo, S. C. Eisenstat and T. Steihaug, Inexact Newton methods, SIAM J. Numer. Anal. 19 (1982), 400-408. MR 650059 (83b:65056)
  • [8] 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.
  • [9] J. E. Dennis, Jr. and E. S. Marwil, Direct secant updates of matrix factorizations, Math. Comp. 38 (1982), 459-476. MR 645663 (83d:65159)
  • [10] J. E. Dennis, Jr. and J. J. Moré, A characterization of superlinear convergence and its application to quasi-Newton methods, Math. Comp. 28 (1974), 549-560. MR 0343581 (49:8322)
  • [11] -, Quasi-Newton methods, motivation and theory, SIAM Rev. 19 (1977), 46-89. MR 0445812 (56:4146)
  • [12] J. E. Dennis, Jr. and R. B. Schnabel, Least change secant updates for quasi-Newton methods, SIAM Rev. 21 (1979), 443-459. MR 545880 (80j:65021)
  • [13] -, Numerical methods for unconstrained optimization and nonlinear equations, Prentice-Hall Series in Comput. Math., Prentice-Hall, N.J., 1983. MR 702023 (85j:65001)
  • [14] J. E. Dennis, Jr. and H. F. Walker, Convergence theorems for least-change secant update methods, SIAM J. Numer. Anal. 18 (1981), 949-987. MR 638993 (83a:65052a)
  • [15] I. S. Duff, A. M. Erisman, and J. K. Reid, Direct methods for sparse matrices, Clarendon Press, Oxford, 1986. MR 892734 (88f:65043)
  • [16] P. E. Gill, G. H. Golub, W. Murray, and M. A. Saunders, Methods for modifying matrix factorizations, Math. Comp. 28 (1974), 505-535. MR 0343558 (49:8299)
  • [17] G. H. Golub and Ch. F. Van Loan, Matrix computations, The Johns Hopkins University Press, Baltimore, 1983. MR 733103 (85h:65063)
  • [18] A. Griewank, The local convergence of Broyden-like methods on Lipschitzian problems in Hilbert spaces, SIAM J. Numer. Anal. 24 (1987), 684-705. MR 888756 (89b:65143)
  • [19] A. Griewank and Ph. L. Toint, On the unconstrained optimization of partially separable functions, Nonlinear Optimization, 1981 (M. J. D. Powell, ed.), Academic Press, New York, 1982. MR 775354
  • [20] -, Partitioned variable metric for large structured optimization problems, Numer. Math. 39 (1982), 119-137. MR 664541 (83k:65054)
  • [21] -, Local convergence analysis for partitioned quasi-Newton updates, Numer. Math. 39 (1982), 429-448. MR 678746 (84b:65062)
  • [22] -, Numerical experiments with partially separable optimization problems, Numerical Analysis (Proceedings Dundee 1983) (D. F. Griffiths, ed.), Lecture Notes in Math., vol. 1066, Springer-Verlag, Berlin, 1984, pp. 203-220. MR 760465 (85h:90102)
  • [23] M. R. Hestenes and E. Stiefel, Methods of conjugate gradients for solving linear systems, J. Res. Nat. Bur. Standards B 49 (1952), 409-436. MR 0060307 (15:651a)
  • [24] G. W. Johnson and N. H. Austria, A quasi-Newton method employing direct secant updates of matrix factorizations, SIAM J. Numer. Anal. 20 (1983), 315-325. MR 694521 (84g:65069)
  • [25] C. T. Kelley and E. W. Sachs, Broyden's method for approximate solution of nonlinear integral equations, J. Integral Equations 9 (1985), 25-43. MR 793102 (86i:65083)
  • [26] K. Levenberg, A method for the solution of certain nonlinear problems in least squares, Quart. J. Appl. Math. 2 (1944), 164-168. MR 0010666 (6:52a)
  • [27] D. G. Luenberger, Linear and nonlinear programming, 2nd ed., Addison-Wesley, Reading, Mass., 1984.
  • [28] D. W. Marquardt, An algorithm for least-squares estimation of nonlinear parameters, SIAM J. Appl. Math. 11 (1963), 431-441. MR 0153071 (27:3040)
  • [29] 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), 131-142. MR 865227 (87j:65059)
  • [30] -, Quasi-Newton methods with factorization scaling for solving sparse nonlinear systems of equations, Computing 38 (1987), 131-141. MR 889958 (89b:65125)
  • [31] -, A family of Quasi-Newton methods with direct secant updates of matrix factorizations, SIAM J. Numer. Anal. (to appear).
  • [32] E. S. Marwil, Exploiting sparsity in Newton-type methods, Cornell Applied Mathematics Ph.D. thesis, 1978.
  • [33] -, Convergence results for Schubert's method for solving sparse nonlinear equations, SIAM J. Numer. Anal. 16 (1979), 588-604. MR 537273 (80i:65057)
  • [34] J. J. Moré and J. A. Trangenstein, On the global convergence of Broyden's method, Math. Comp. 30 (1976), 523-540. MR 0418451 (54:6490)
  • [35] J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York, 1970. MR 0273810 (42:8686)
  • [36] O. Østerby and Z. Zlatev, Direct methods for sparse matrices, Lecture Notes in Comput. Sci., vol. 157, Springer-Verlag, Berlin, Heidelberg, New York, and Tokyo, 1983. MR 716136 (85e:65019)
  • [37] M. J. D. Powell, A new algorithm for unconstrained optimization, Nonlinear Programming (J. B. Rosen, O. L. Mangasarian, and K. Ritter, eds.), Academic Press, New York, 1970, pp. 31-65. MR 0272162 (42:7043)
  • [38] E. Sachs, Broyden's method in Hilbert space, Math. Programming 35 (1986), 71-82. MR 842635 (87i:90331)
  • [39] L. K. Schubert, Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27-30. MR 0258276 (41:2923)
  • [40] H. Schwetlick, Numerische Lösung nichtlinearer Gleichungen, Deutscher Verlag der Wissenschaften, Berlin, 1978. MR 519682 (80f:65061)
  • [41] Ph. L. Toint, On sparse and symmetric matrix updating subject to a linear equation, Math. Comp. 13 (1977), 954-961. MR 0455338 (56:13577)
  • [42] Ph. L. Toint, Some numerical results using a sparse matrix updating formula in unconstrained optimization, Math. Comp. 32 (1978), 839-851. MR 0483452 (58:3453)
  • [43] -, Numerical solution of large sets of algebraic nonlinear equations, Math. Comp. 46 (1986), 175-189. MR 815839 (87d:65064)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65H10, 90C30

Retrieve articles in all journals with MSC: 65H10, 90C30


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1990-1023050-5
Keywords: Nonlinear simultaneous equations, Least Change Secant Updates, quasi-Newton methods, Inexact Newton methods
Article copyright: © Copyright 1990 American Mathematical Society

American Mathematical Society