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.

- C. G. Broyden,
*A class of methods for solving nonlinear simultaneous equations*, Math. Comp.**19**(1965), 577–593. MR**198670**, DOI https://doi.org/10.1090/S0025-5718-1965-0198670-6 - 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**433870**
A. BUCKLEY, - 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**, DOI https://doi.org/10.1137/1021091 - 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** - R. Fletcher and M. J. D. Powell,
*A rapidly convergent descent method for minimization*, Comput. J.**6**(1963/64), 163–168. MR**152116**, DOI https://doi.org/10.1093/comjnl/6.2.163
R. FLETCHER, “A new approach to variable metric algorithms,” - Donald Goldfarb,
*A family of variable-metric methods derived by variational means*, Math. Comp.**24**(1970), 23–26. MR**258249**, DOI https://doi.org/10.1090/S0025-5718-1970-0258249-6 - D. Goldfarb,
*Generating conjugate directions without line searches using factorized variable metric updating formulas*, Math. Programming**13**(1977), no. 1, 94–110. MR**503799**, DOI https://doi.org/10.1007/BF01584327 - J. Greenstadt,
*Variations on variable-metric methods. (With discussion)*, Math. Comp.**24**(1970), 1–22. MR**258248**, DOI https://doi.org/10.1090/S0025-5718-1970-0258248-4
M. D. HEBDEN, - 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**, DOI https://doi.org/10.1007/BF01582091 - 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**
R. B. SCHNABEL, - L. K. Schubert,
*Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian*, Math. Comp.**24**(1970), 27–30. MR**258276**, DOI https://doi.org/10.1090/S0025-5718-1970-0258276-9 - D. F. Shanno,
*Conditioning of quasi-Newton methods for function minimization*, Math. Comp.**24**(1970), 647–656. MR**274029**, DOI https://doi.org/10.1090/S0025-5718-1970-0274029-X - David F. Shanno,
*Conjugate gradient methods with inexact searches*, Math. Oper. Res.**3**(1978), no. 3, 244–256. MR**506662**, DOI https://doi.org/10.1287/moor.3.3.244 - 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**525744**, DOI https://doi.org/10.1007/BF00933517
D. F. SHANNO & K. H. PHUA, “Minimization of unconstrained multivariate functions,” - Ph. L. Toint,
*On sparse and symmetric matrix updating subject to a linear equation*, Math. Comp.**31**(1977), no. 140, 954–961. MR**455338**, DOI https://doi.org/10.1090/S0025-5718-1977-0455338-4 - Ph. L. Toint,
*Some numerical results using a sparse matrix updating formula in unconstrained optimization*, Math. Comp.**32**(1978), no. 143, 839–851. MR**483452**, DOI https://doi.org/10.1090/S0025-5718-1978-0483452-7

*A Combined Conjugate-Gradient Quasi-Newton Minimization Algorithm*, Working Paper, Mathematics Department, Concordia University, Montreal, Quebec, Canada, 1977. W. C. DAVIDON,

*Variable Metric Method for Minimization*, Report ANL-5990 Rev (1959), Argonne National Laboratories, Argonne, Ill., 1959. 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.

*Comput. J.*, v. 13, 1970, pp. 317-322.

*An Algorithm for Minimization Using Exact Second Derivatives*, Report T. P. 515, AERE, Harwell, 1973. E. S. MARWIL,

*Exploiting Sparsity in Newton-Like Methods*, Report TR78-335, Dept. of Computer Science, Cornell University, Ithaca, New York, 1978. 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.

*Analyzing and Improving Quasi-Newton Methods for Unconstrained Optimization*, Report TR77-320, Dept. of Computer Science, Cornell University, Ithaca, New York, 1977.

*ACM Trans. Math. Software*, v. 2, 1976, pp. 87-94.

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

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

Additional Information

Article copyright:
© Copyright 1980
American Mathematical Society