Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)

 
 

 

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.


References [Enhancements On Off] (What's this?)

  • [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)

Similar Articles

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

American Mathematical Society