On the sparse and symmetric least-change secant update

Author:
Trond Steihaug

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

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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.

**[1]**Owe Axelsson,*Solution of linear systems of equations: iterative methods*, Sparse matrix techniques (Adv. Course, Technical Univ. Denmark, Copenhagen, 1976) Springer, Berlin, 1977, pp. 1–51. Lecture Notes in Math., Vol. 572. MR**0448834****[2]**È¦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**, https://doi.org/10.1007/BF01930845**[3]**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**0341853****[4]**Ron S. Dembo, Stanley C. Eisenstat, and Trond Steihaug,*Inexact Newton methods*, SIAM J. Numer. Anal.**19**(1982), no. 2, 400–408. MR**650059**, https://doi.org/10.1137/0719025**[5]**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**0343581**, https://doi.org/10.1090/S0025-5718-1974-0343581-1**[6]**J. E. Dennis Jr. and Jorge J. Moré,*Quasi-Newton methods, motivation and theory*, SIAM Rev.**19**(1977), no. 1, 46–89. MR**0445812**, https://doi.org/10.1137/1019005**[7]**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**, https://doi.org/10.1137/1021091**[8]**S. C. Eisenstat & T. Steihaug,*Local Analysis of Inexact Quasi-Newton Methods*, Department of Mathematical Sciences TR 82-7, Rice University, Houston, 1982.**[9]**E. S. Marwil,*Exploiting Sparsity in Newton-Like Methods*, Ph.D. Thesis, Cornell University, Computer Science Research Report TR 78-335, 1978.**[10]**J. M. Ortega and W. C. Rheinboldt,*Iterative solution of nonlinear equations in several variables*, Academic Press, New York-London, 1970. MR**0273810****[11]**M. J. D. Powell,*Convergence properties of a class of minimization algorithms*, Nonlinear programming, 2 (Proc. Sympos. Special Interest Group on Math. Programming, Univ. Wisconsin, Madison, Wis., 1974) Academic Press, New York, 1974, pp. 1–27. MR**0386270****[12]**T. Steihaug,*Quasi-Newton Methods for Large Scale Nonlinear Problems*, Ph.D. Thesis, Yale University, SOM Technical Report #49, 1980.**[13]**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**, https://doi.org/10.1137/0720042**[14]**T. Steihaug,*Damped Inexact Quasi-Newton Methods*, Department of Mathematical Sciences TR 81-3, Rice University, Houston, 1981.**[15]**Ph. L. Toint,*On sparse and symmetric matrix updating subject to a linear equation*, Math. Comp.**31**(1977), no. no 140, 954–961. MR**0455338**, https://doi.org/10.1090/S0025-5718-1977-0455338-4**[16]**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**, https://doi.org/10.1137/0716076

Retrieve articles in *Mathematics of Computation*
with MSC:
65H05,
65F50

Retrieve articles in all journals with MSC: 65H05, 65F50

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1984-0736450-2

Article copyright:
© Copyright 1984
American Mathematical Society