Some numerical results using a sparse matrix updating formula in unconstrained optimization

Author:
Ph. L. Toint

Journal:
Math. Comp. **32** (1978), 839-851

MSC:
Primary 65K05

DOI:
https://doi.org/10.1090/S0025-5718-1978-0483452-7

MathSciNet review:
0483452

Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: This paper presents a numerical comparison between algorithms for unconstrained optimization that take account of sparsity in the second derivative matrix of the objective function. Some of the methods included in the comparison use difference approximation schemes to evaluate the second derivative matrix and others use an approximation to it which is updated regularly using the changes in the gradient. These results show what method to use in what circumstances and also suggest interesting future developments.

**[1]**A. R. CURTIS, M. J. D. POWELL & J. K. REID, "On the estimation of sparse Jacobian matrices,"*J. Inst. Math. Appl.*, v. 13, 1974, pp. 117-119.**[2]**W. C. DAVIDON,*Variable Metric Method for Minimization*, A. N. L. Research and Development Report, ANL-5990 (Rev.), 1959.**[3]**J. E. Dennis Jr. and Jorge J. Moré,*Quasi-Newton methods, motivation and theory*, SIAM Rev.**19**(1977), no. 1, 46–89. MR**445812**, https://doi.org/10.1137/1019005**[4]**R. Fletcher and M. J. D. Powell,*A rapidly convergent descent method for minimization*, Comput. J.**6**(1963/64), 163–168. MR**152116**, https://doi.org/10.1093/comjnl/6.2.163**[5]**M. D. HEBDEN,*An Algorithm for Minimization Using Exact Second Derivatives*, Report T. P. 515, AERE, Harwell, 1973.**[6]**H. Y. Huang,*Unified approach to quadratically convergent algorithms for function minimization*, J. Optim. Theory Appl.**5**(1970), 405–423. MR**288939**, https://doi.org/10.1007/BF00927440**[7]**M. R. OSBORNE, "Variational methods and extrapolation procedures," in*Methods in Computational Physics*(R. S. Anderssen & R. O. Watts, Editors), Univ. of Queensland Press, Brisbane, 1975.**[8]**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****[9]**M. J. D. POWELL,*A Fortran Subroutine for Unconstrained Minimization, Requiring First Derivatives of the Objective Function*, Report R-6469, AERE, Harwell, 1970.**[10]**M. J. D. Powell,*Convergence properties of a class of minimization algorithms*, Nonlinear programming, 2 (Proc. Sympos. Special Interest Group on Math. Programming, Univ. Wisconsin, Madison, Wis., 1974) Academic Press, New York, 1974, pp. 1–27. MR**0386270****[11]**M. J. D. Powell,*A view of unconstrained optimization*, Optimization in action (Proc. Conf., Univ. Bristol, Bristol, 1975), Academic Press, London, 1976, pp. 117–152. MR**0431680****[12]**J. K. REID,*Two Fortran Subroutines for Direct Solution of Linear Equations, whose Matrix is Sparse, Symmetric and Positive Definite*, Report R-7119, AERE, Harwell, 1972.**[13]**L. K. Schubert,*Modification of a quasi-Newton method for nonlinear equations with a sparse Jacobian*, Math. Comp.**24**(1970), 27–30. MR**258276**, https://doi.org/10.1090/S0025-5718-1970-0258276-9**[14]**Ph. L. Toint,*On sparse and symmetric matrix updating subject to a linear equation*, Math. Comp.**31**(1977), no. no 14, no 140, 954–961. MR**455338**, https://doi.org/10.1090/S0025-5718-1977-0455338-4

Retrieve articles in *Mathematics of Computation*
with MSC:
65K05

Retrieve articles in all journals with MSC: 65K05

Additional Information

DOI:
https://doi.org/10.1090/S0025-5718-1978-0483452-7

Keywords:
Numerical results,
sparsity,
quasi-Newton methods,
unconstrained optimization

Article copyright:
© Copyright 1978
American Mathematical Society