Abstract:To find the sparse and symmetric n by n least-change secant update we have to solve a consistent linear system of n equations in n unknowns, where the coefficient matrix is symmetric and positive semidefinite. We give bounds on the eigenvalues of the coefficient matrix and show that the preconditioned conjugate gradient method is a very efficient method for solving the linear equation. By solving the linear system only approximately, we generate a family of sparse and symmetric updates with a residual in the secant equation. We address the question of how accurate a solution is needed not to impede the convergence of quasi-Newton methods using the approximate least-change update. We show that the quasi-Newton methods are locally and superlinearly convergent after one or more preconditioned conjugate gradient iterations.
- Owe Axelsson, Solution of linear systems of equations: iterative methods, Sparse matrix techniques (Adv. Course, Technical Univ. Denmark, Copenhagen, 1976) Lecture Notes in Math., Vol. 572, Springer, Berlin, 1977, pp. 1–51. MR 0448834
- Ȧke Björck and Tommy Elfving, Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations, BIT 19 (1979), no. 2, 145–163. MR 537775, DOI 10.1007/BF01930845
- 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
- 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. 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 S. C. Eisenstat & T. Steihaug, Local Analysis of Inexact Quasi-Newton Methods, Department of Mathematical Sciences TR 82-7, Rice University, Houston, 1982. E. S. Marwil, Exploiting Sparsity in Newton-Like Methods, Ph.D. Thesis, Cornell University, Computer Science Research Report TR 78-335, 1978.
- J. M. Ortega and W. C. Rheinboldt, Iterative solution of nonlinear equations in several variables, Academic Press, New York-London, 1970. MR 0273810
- M. J. D. Powell, Convergence properties of a class of minimization algorithms, Nonlinear programming, 2 (Proc. Special Interest Group on Math. Programming Sympos., Univ. Wisconsin, Madison, Wis., 1974) Academic Press, New York, 1974, pp. 1–27. MR 0386270 T. Steihaug, Quasi-Newton Methods for Large Scale Nonlinear Problems, Ph.D. Thesis, Yale University, SOM Technical Report #49, 1980.
- Trond Steihaug, The conjugate gradient method and trust regions in large scale optimization, SIAM J. Numer. Anal. 20 (1983), no. 3, 626–637. MR 701102, DOI 10.1137/0720042 T. Steihaug, Damped Inexact Quasi-Newton Methods, Department of Mathematical Sciences TR 81-3, Rice University, Houston, 1981.
- 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. Toint, On the superlinear convergence of an algorithm for solving a sparse minimization problem, SIAM J. Numer. Anal. 16 (1979), no. 6, 1036–1045. MR 551324, DOI 10.1137/0716076
- © Copyright 1984 American Mathematical Society
- Journal: Math. Comp. 42 (1984), 521-533
- MSC: Primary 65H05; Secondary 65F50
- DOI: https://doi.org/10.1090/S0025-5718-1984-0736450-2
- MathSciNet review: 736450