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.

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

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