Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

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

 
 

 

On variable-metric methods for sparse Hessians


Author: D. F. Shanno
Journal: Math. Comp. 34 (1980), 499-514
MSC: Primary 65K10; Secondary 15A57, 90C30
DOI: https://doi.org/10.1090/S0025-5718-1980-0559198-2
MathSciNet review: 559198
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The relationship between variable-metric methods derived by norm minimization and those derived by symmetrization of rank-one updates for sparse systems is studied, and an analogue of Dennis's nonsparse symmetrization formula derived. A new method of using norm minimization to produce a sparse analogue of any nonsparse variable-metric method is proposed. The sparse BFGS generated by this method is tested against the sparse PSB and variable-memory conjugate gradient methods, with computational experience uniformly favoring the sparse BFGS.


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] C. G. BROYDEN, ``The convergence of a class of double rank minimization algorithms 2, the new algorithm,'' J. Inst. Math. Appl., v. 6, 1970, pp. 222-231. MR 0433870 (55:6841)
  • [3] A. BUCKLEY, A Combined Conjugate-Gradient Quasi-Newton Minimization Algorithm, Working Paper, Mathematics Department, Concordia University, Montreal, Quebec, Canada, 1977.
  • [4] W. C. DAVIDON, Variable Metric Method for Minimization, Report ANL-5990 Rev (1959), Argonne National Laboratories, Argonne, Ill., 1959.
  • [5] J. E. DENNIS, ``On some methods based on Broyden's secant approximation to the Hessian,'' Numerical Methods for Nonlinear Optimization (F. A. Lootsma, Ed.), Academic Press, London, 1972, pp. 19-34.
  • [6] J. E. DENNIS, JR. & R. B. SCHNABEL, Least Change Secant Updates for Quasi-Newton Methods, Report CS-CU-132-78, Dept. of Computer Science, University of Colorado, Boulder, July, 1978. MR 545880 (80j:65021)
  • [7] A. V. FIACCO & G. P. MCCORMICK, Nonlinear Programming, Sequential Unconstrained Minimization Techniques, Wiley, New York, 1968, pp. 170-172. MR 0243831 (39:5152)
  • [8] R. FLETCHER & M. J. D. POWELL, ``A rapidly convergent descent method for minimization,'' Comput. J., v. 6, 1963, pp. 163-168. MR 0152116 (27:2096)
  • [9] R. FLETCHER, ``A new approach to variable metric algorithms,'' Comput. J., v. 13, 1970, pp. 317-322.
  • [10] D. GOLDFARB, ``A family of variable-metric methods derived by variational means,'' Math. Comp., v. 24, 1970, pp. 23-26. MR 0258249 (41:2896)
  • [11] D. GOLDFARB, ``Generating conjugate directions without line searches using factorized variable-metric updating formulas,'' Math. Programming, v. 13, 1977, pp. 94-110. MR 0503799 (58:20447)
  • [12] J. GREENSTADT, ``Variations on variable-metric methods,'' Math. Comp., v. 24, 1970, pp. 1-22. MR 0258248 (41:2895)
  • [13] M. D. HEBDEN, An Algorithm for Minimization Using Exact Second Derivatives, Report T. P. 515, AERE, Harwell, 1973.
  • [14] E. S. MARWIL, Exploiting Sparsity in Newton-Like Methods, Report TR78-335, Dept. of Computer Science, Cornell University, Ithaca, New York, 1978.
  • [15] J. J. MORÉ, B. S. GARBOW & K. E. HILLSTROM, Testing Unconstrained Optimization Software, Report TM-324, Applied Mathematics Division, Argonne National Laboratory, Argonne, Ill., 1978.
  • [16] J. J. MORÉ & D. C. SORENSEN, On the Use of Directions of Negative Curvature in a Modified Newton Method, Report TM-319, Applied Mathematics Division, Argonne National Laboratory, Argonne, Ill., 1977. MR 517757 (80b:90119)
  • [17] M. J. D. POWELL, ``A new algorithm for unconstrained optimization,'' Nonlinear Programming (J. B. Rosen, O. L. Mangasarian & K. Ritter, Eds.), Academic Press, New York, 1970. MR 0272162 (42:7043)
  • [18] R. B. SCHNABEL, Analyzing and Improving Quasi-Newton Methods for Unconstrained Optimization, Report TR77-320, Dept. of Computer Science, Cornell University, Ithaca, New York, 1977.
  • [19] 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)
  • [20] D. F. SHANNO, ``Conditioning of quasi-Newton methods for function minimization,'' Math. Comp., v. 24, 1970, pp. 647-656. MR 0274029 (42:8905)
  • [21] D. F. SHANNO, ``Conjugate gradient methods with inexact searches,'' Math. Oper. Res., v. 3, 1978, pp. 244-256. MR 506662 (80d:65082)
  • [22] D. F. SHANNO & K. H. PHUA, ``Numerical comparison of several variable-metric algorithms,'' J. Optim. Theory Appl., v. 25, 1978, pp. 507-518. MR 0525744 (58:26017)
  • [23] D. F. SHANNO & K. H. PHUA, ``Minimization of unconstrained multivariate functions,'' ACM Trans. Math. Software, v. 2, 1976, pp. 87-94.
  • [24] 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)
  • [25] PH. L. TOINT, ``Some numerical results using a sparse matrix updating formula in unconstrained optimization,'' Math. Comp., v. 32, 1978, pp. 839-852. MR 0483452 (58:3453)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC: 65K10, 15A57, 90C30

Retrieve articles in all journals with MSC: 65K10, 15A57, 90C30


Additional Information

DOI: https://doi.org/10.1090/S0025-5718-1980-0559198-2
Article copyright: © Copyright 1980 American Mathematical Society

American Mathematical Society