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]**O. Axelsson, "Solution of linear systems of equations: iterative methods,"*Sparse Matrix Techniques*(V. A. Barker, ed.), Lecture Notes in Math., vol. 572, Springer-Verlag, New York, 1976, pp. 1-51. MR**0448834 (56:7139)****[2]**A. Björk & T. Elfving, "Accelerated projection methods for computing pseudoinverse solutions of systems of linear equations,"*BIT*, v. 19, 1979, pp. 145-163. MR**537775 (80e:65048)****[3]**C. G. Broyden, J. E. Dennis, Jr. & J. J. Moré, "On the local and superlinear convergence of quasi-Newton methods,"*J. Inst. Math. Appl.*, v. 12, 1973, pp. 223-245. MR**0341853 (49:6599)****[4]**R. S. Dembo, S. C. Eisenstat & T. Steihaug, "Inexact Newton methods,"*SIAM J. Numer. Anal.*, v. 19, 1982, pp. 400-408. MR**650059 (83b:65056)****[5]**J. E. Dennis, Jr. & J. J. Moré, "A characterization of superlinear convergence and its application to quasi-Newton methods,"*Math. Comp.*, v. 28, 1974, pp. 549-560. MR**0343581 (49:8322)****[6]**J. E. Dennis, Jr. & J. J. Moré, "Quasi-Newton methods, motivation and theory,"*SIAM Rev.*, v. 19, 1977, pp. 46-89. MR**0445812 (56:4146)****[7]**J. E. Dennis, Jr. & R. B. Schnabel, "Least change secant updates for quasi-Newton methods,"*SIAM Rev.*, v. 21, 1979, pp. 443-459. MR**545880 (80j:65021)****[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 & W. C. Rheinboldt,*Iterative Solution of Nonlinear Equations in Several Variables*, Academic Press, New York, 1970. MR**0273810 (42:8686)****[11]**M. J. D. Powell, "Convergence properties of a class of minimization algorithms,"*Nonlinear Programming*, Vol. 2 (O. L. Mangasarian, R. R. Meyer, and S. M. Robinson, eds.), Academic Press, New York, 1975, pp. 1-27. MR**0386270 (52:7128)****[12]**T. Steihaug,*Quasi-Newton Methods for Large Scale Nonlinear Problems*, Ph.D. Thesis, Yale University, SOM Technical Report #49, 1980.**[13]**T. Steihaug, "The conjugate gradient method and trust regions in large scale optimization,"*SIAM J. Numer. Anal.*, v. 20, 1983, pp. 626-637. MR**701102 (84g:49047)****[14]**T. Steihaug,*Damped Inexact Quasi-Newton Methods*, Department of Mathematical Sciences TR 81-3, Rice University, Houston, 1981.**[15]**P. L. Toint, "On sparse and symmetric matrix updating subject to a linear equation,"*Math. Comp.*, v. 31, 1977, pp. 954-961. MR**0455338 (56:13577)****[16]**P. L. Toint, "On the superlinear convergence of an algorithm for solving a sparse minimization problem,"*SIAM J. Numer. Anal.*, v. 16, 1979, pp. 1036-1045. MR**551324 (81f:65046)**

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