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

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.

**[1]**C. G. Broyden,*A class of methods for solving nonlinear simultaneous equations*, Math. Comp.**19**(1965), 577–593. MR**0198670**, https://doi.org/10.1090/S0025-5718-1965-0198670-6**[2]**C. G. Broyden,*The convergence of a class of double-rank minimization algorithms. II. The new algorithm*, J. Inst. Math. Appl.**6**(1970), 222–231. MR**0433870****[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. and R. B. Schnabel,*Least change secant updates for quasi-Newton methods*, SIAM Rev.**21**(1979), no. 4, 443–459. MR**545880**, https://doi.org/10.1137/1021091**[7]**Anthony V. Fiacco and Garth P. McCormick,*Nonlinear programming: Sequential unconstrained minimization techniques*, John Wiley and Sons, Inc., New York-London-Sydney, 1968. MR**0243831****[8]**R. Fletcher and M. J. D. Powell,*A rapidly convergent descent method for minimization*, Comput. J.**6**(1963/1964), 163–168. MR**0152116**, https://doi.org/10.1093/comjnl/6.2.163**[9]**R. FLETCHER, ``A new approach to variable metric algorithms,''*Comput. J.*, v. 13, 1970, pp. 317-322.**[10]**Donald Goldfarb,*A family of variable-metric methods derived by variational means*, Math. Comp.**24**(1970), 23–26. MR**0258249**, https://doi.org/10.1090/S0025-5718-1970-0258249-6**[11]**D. Goldfarb,*Generating conjugate directions without line searches using factorized variable metric updating formulas*, Math. Programming**13**(1977), no. 1, 94–110. MR**0503799**, https://doi.org/10.1007/BF01584327**[12]**J. Greenstadt,*Variations on variable-metric methods. (With discussion)*, Math. Comp.**24**(1970), 1–22. MR**0258248**, https://doi.org/10.1090/S0025-5718-1970-0258248-4**[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]**Jorge J. Moré and Danny C. Sorensen,*On the use of directions of negative curvature in a modified Newton method*, Math. Programming**16**(1979), no. 1, 1–20. MR**517757**, https://doi.org/10.1007/BF01582091**[17]**M. J. D. Powell,*A new algorithm for unconstrained optimization*, Nonlinear Programming (Proc. Sympos., Univ. of Wisconsin, Madison, Wis., 1970) Academic Press, New York, 1970, pp. 31–65. MR**0272162****[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.**24**(1970), 27–30. MR**0258276**, https://doi.org/10.1090/S0025-5718-1970-0258276-9**[20]**D. F. Shanno,*Conditioning of quasi-Newton methods for function minimization*, Math. Comp.**24**(1970), 647–656. MR**0274029**, https://doi.org/10.1090/S0025-5718-1970-0274029-X**[21]**David F. Shanno,*Conjugate gradient methods with inexact searches*, Math. Oper. Res.**3**(1978), no. 3, 244–256. MR**506662**, https://doi.org/10.1287/moor.3.3.244**[22]**D. F. Shanno and K. H. Phua,*Numerical comparison of several variable-metric algorithms*, J. Optim. Theory Appl.**25**(1978), no. 4, 507–518. MR**0525744**, https://doi.org/10.1007/BF00933517**[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 matrix updating subject to a linear equation*, Math. Comp.**31**(1977), no. no 140, 954–961. MR**0455338**, https://doi.org/10.1090/S0025-5718-1977-0455338-4**[25]**Ph. L. Toint,*Some numerical results using a sparse matrix updating formula in unconstrained optimization*, Math. Comp.**32**(1978), no. 143, 839–851. MR**0483452**, https://doi.org/10.1090/S0025-5718-1978-0483452-7

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