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 Free Access

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.

- 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** - Ȧ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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/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 https://doi.org/10.1137/1021091
S. C. Eisenstat & T. Steihaug, - 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. Sympos. Special Interest Group on Math. Programming, Univ. Wisconsin, Madison, Wis., 1974) Academic Press, New York, 1974, pp. 1–27. MR**0386270**
T. Steihaug, - 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 https://doi.org/10.1137/0720042
T. Steihaug, - 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 https://doi.org/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 https://doi.org/10.1137/0716076

*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.

*Quasi-Newton Methods for Large Scale Nonlinear Problems*, Ph.D. Thesis, Yale University, SOM Technical Report #49, 1980.

*Damped Inexact Quasi-Newton Methods*, Department of Mathematical Sciences TR 81-3, Rice University, Houston, 1981.

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

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

Additional Information

Article copyright:
© Copyright 1984
American Mathematical Society