A sparse quasi-Newton update derived variationally with a nondiagonally weighted Frobenius norm

Author:
Ph. L. Toint

Journal:
Math. Comp. **37** (1981), 425-433

MSC:
Primary 65F30; Secondary 15A24, 65K10

DOI:
https://doi.org/10.1090/S0025-5718-1981-0628706-6

MathSciNet review:
628706

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: The problem of symmetric sparse updating is considered from a variational point of view and a new class of sparse symmetric quasi-Newton updating formulae is derived. This class results from the use of a nondiagonally weighted Frobenius norm. The computation of the update involves only one positive definite and symmetric linear system that has the same sparsity pattern as the problem itself.

**[1]**C. G. Broyden, "A class of methods for solving nonlinear simultaneous equations,"*Math. Comp.*, v. 19, 1965, pp. 577-593. MR**0198670 (33:6825)****[2]**W. C. Davidon,*Variable Metric Method for Minimization*, Report #ANL-5990, (Rev.) A.N.L. Research and Development Report, 1959.**[3]**J. E. Dennis & J. Moré, "Quasi-Newton methods, motivation and theory,"*SIAM Rev.*, v. 19, 1977, pp. 46-89. MR**0445812 (56:4146)****[4]**J. E. Dennis & R. B. Schnabel,*Least Change Secant Updates for Quasi-Newton Methods*, Report #TR78-344, Dept. of Computer Science, Cornell Univ., 1978.**[5]**J. E. Dennis & H. F. Walker,*Convergence Theorems for Least Change Secant Update Methods*, Report #TR476-(141-171-163)-2, Dept. of Mathematical Science, Rice University, Houston, 1979.**[6]**D. Goldfarb, "A family of variable metric methods derived by variational means,"*Math. Comp.*, v. 24, 1970, pp. 23-26. MR**0258249 (41:2896)****[7]**J. Greenstadt, "Variations on variable metric methods,"*Math. Comp.*, v. 24, 1970, pp. 1-22. MR**0258248 (41:2895)****[8]**H. Y. Huang, "Unified approach to quadratically convergent algorithms for function minimization,"*J. Optim. Theory Appl.*, v. 5, 1970, pp. 405-423. MR**0288939 (44:6134)****[9]**E. S. Marwil,*Exploiting Sparsity in Newton-Like Methods*, Ph. D. Thesis, Cornell Univ., 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, "A new algorithm for unconstrained optimization,"*Nonlinear Programming*(J. B. Rosen, O. L. Mangasarian and K. Ritter, Eds.), Academic Press, New York, 1970, pp. 31-65. MR**0272162 (42:7043)****[12]**M. J. D. Powell,*Quasi-Newton Formulae for Sparse Second Derivative Matrices*, Report #DAMTP 1979/NA7, Dept. of Applied Mathematics and Theoretical Physics, Cambridge University (G.B.), 1979.**[13]**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)****[14]**D. F. Shanno,*On Variable-Metric Methods for Sparse Hessians, The New Method*, Report #MIS TR 27, Dept. of Management Information Systems, University of Arizona, Tuscon, 1978.**[15]**D. F. Shanno & K. H. Phua, "Matrix conditioning and nonlinear optimization,"*Math. Programming*, v. 14, 1978, pp. 149-160. MR**0474819 (57:14450)****[16]**Ph. L. Toint, "On sparse and symmetric updating subject to a linear equation,"*Math. Comp.*, v. 31, 1977, pp. 954-961. MR**0455338 (56:13577)****[17]**Ph. L. Toint, "On the superlinear convergence of an algorithm for solving a sparse minimization problem,"*SIAM J. Numer. Anal.*, v. 16, 1979. MR**551324 (81f:65046)****[18]**Ph. L. Toint, "A note about sparsity exploiting quasi-Newton updates,"*Math. Programming*, v. 21, 1981. MR**623836 (82i:90103)**

Retrieve articles in *Mathematics of Computation*
with MSC:
65F30,
15A24,
65K10

Retrieve articles in all journals with MSC: 65F30, 15A24, 65K10

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1981-0628706-6

Keywords:
Nonlinear optimization,
sparsity,
matrix updating

Article copyright:
© Copyright 1981
American Mathematical Society