An explicit quasi-Newton update for sparse optimization calculations

Author:
Angelo Lucia

Journal:
Math. Comp. **40** (1983), 317-322

MSC:
Primary 65K05

DOI:
https://doi.org/10.1090/S0025-5718-1983-0679448-4

MathSciNet review:
679448

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: A new quasi-Newton updating formula for sparse optimization calculations is presented. It makes combined use of a simple strategy for fixing symmetry and a Schubert correction to the upper triangle of a permuted Hessian approximation. Interesting properties of this new update are that it is closed form and that it does not satisfy the secant condition at every iteration of the calculations. Some numerical results are given that show that this update compares favorably with the sparse PSB update and appears to have a superlinear rate of convergence.

**[1]**J. E. Dennis & 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)****[2]**J. E. Dennis & R. B. Schnabel, "Least change secant updates for quasi-Newton methods,"*SIAM Rev.*, v. 21, 1979, pp. 443-459. MR**545880 (80j:65021)****[3]**S. C. Eisenstat, M. C. Gursky, M. H. Schultz & A. H. Sherman,*Yale Sparse Matrix Package--The Symmetric Codes*, Report No. 112, Dept. of Computer Science, Yale University, New Haven, Conn., 1977.**[4]**M. D. Hebden,*An Algorithm for Minimization Using Exact Second Derivatives*, Report No. T.P. 515, A.E.R.E. Harwell, 1973.**[5]**E. S. Marwil,*Exploiting Sparsity in Newton-Like Methods*, Ph.D. Thesis, Cornell University, Ithaca, N.Y., 1978.**[6]**L. K. Schubert, "Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian,"*Math. Comp.*, v. 24, 1970, pp. 27-30. MR**0258276 (41:2923)****[7]**D. F. Shanno, "On variable metric methods for sparse Hessians,"*Math. Comp.*, v. 34, 1980, pp. 499-514. MR**559198 (81j:65077)****[8]**Ph. 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)****[9]**Ph. L. Toint, "Some numerical results using a sparse matrix updating formula in unconstrained optimization,"*Math. Comp.*, v. 32, 1978, pp. 839-851. MR**0483452 (58:3453)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65K05

Retrieve articles in all journals with MSC: 65K05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1983-0679448-4

Article copyright:
© Copyright 1983
American Mathematical Society