Some numerical results using a sparse matrix updating formula in unconstrained optimization
Author:
Ph. L. Toint
Journal:
Math. Comp. 32 (1978), 839851
MSC:
Primary 65K05
MathSciNet review:
0483452
Fulltext 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. 117119.
 [2]
W. C. DAVIDON, Variable Metric Method for Minimization, A. N. L. Research and Development Report, ANL5990 (Rev.), 1959.
 [3]
J.
E. Dennis Jr. and Jorge
J. Moré, QuasiNewton methods, motivation and theory,
SIAM Rev. 19 (1977), no. 1, 46–89. MR 0445812
(56 #4146)
 [4]
R.
Fletcher and M.
J. D. Powell, A rapidly convergent descent method for
minimization, Comput. J. 6 (1963/1964),
163–168. MR 0152116
(27 #2096)
 [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. Optimization Theory Appl.
5 (1970), 405–423. MR 0288939
(44 #6134)
 [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
(42 #7043)
 [9]
M. J. D. POWELL, A Fortran Subroutine for Unconstrained Minimization, Requiring First Derivatives of the Objective Function, Report R6469, 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
(52 #7128)
 [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
(55 #4675)
 [12]
J. K. REID, Two Fortran Subroutines for Direct Solution of Linear Equations, whose Matrix is Sparse, Symmetric and Positive Definite, Report R7119, AERE, Harwell, 1972.
 [13]
L.
K. Schubert, Modification of a quasiNewton method
for nonlinear equations with a sparse Jacobian, Math. Comp. 24 (1970), 27–30. MR 0258276
(41 #2923), http://dx.doi.org/10.1090/S00255718197002582769
 [14]
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
(56 #13577), http://dx.doi.org/10.1090/S00255718197704553384
 [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. 117119.
 [2]
 W. C. DAVIDON, Variable Metric Method for Minimization, A. N. L. Research and Development Report, ANL5990 (Rev.), 1959.
 [3]
 J. E. DENNIS & J. MORÉ, "Quasi Newton methods, motivation and theory," SIAM Rev., v. 19, 1977, pp. 4689. MR 0445812 (56:4146)
 [4]
 R. FLETCHER & M. J. D. POWELL, "A rapidly convergent descent method for minimization," Comput. J., v. 6, 1963, pp. 163168. MR 0152116 (27:2096)
 [5]
 M. D. HEBDEN, An Algorithm for Minimization Using Exact Second Derivatives, Report T. P. 515, AERE, Harwell, 1973.
 [6]
 H. Y. HUANG, "Unified quadratically convergent algorithms for function minimization," J. Optimization Theory Appl., v. 5, 1970, No. 6. MR 0288939 (44:6134)
 [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, "Anew algorithm for unconstrained optimization" in Nonlinear Programming (J. B. Rosen, O. L. Mangasarian & K. Ritter, Editors), Academic Press, New York, 1970. MR 0272162 (42:7043)
 [9]
 M. J. D. POWELL, A Fortran Subroutine for Unconstrained Minimization, Requiring First Derivatives of the Objective Function, Report R6469, AERE, Harwell, 1970.
 [10]
 M. J. D. POWELL, "Convergence properties of a class of minimization algorithms" in Nonlinear Programming, 2 (O. L. Mangasarian, R. R. Meyer & S. M. Robinson, Editors), Academic Press, New York, 1975. MR 0386270 (52:7128)
 [11]
 M. J. D. POWELL, "A view of unconstrained optimization" in Optimization in Action (L.C.W. Dixon, Editor), Academic Press, New York, 1976. MR 0431680 (55:4675)
 [12]
 J. K. REID, Two Fortran Subroutines for Direct Solution of Linear Equations, whose Matrix is Sparse, Symmetric and Positive Definite, Report R7119, AERE, Harwell, 1972.
 [13]
 L. K. SCHUBERT, "Modification of a quasiNewton method for nonlinear equations with a sparse Jacobian," Math. Comp., v. 24, 1970, pp. 2730. MR 0258276 (41:2923)
 [14]
 Ph. L. TOINT, "On sparse and symmetric matrix updating subject to a linear equation," Math. Comp., v. 31, 1977, pp. 954961. MR 0455338 (56:13577)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
65K05
Retrieve articles in all journals
with MSC:
65K05
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718197804834527
PII:
S 00255718(1978)04834527
Keywords:
Numerical results,
sparsity,
quasiNewton methods,
unconstrained optimization
Article copyright:
© Copyright 1978
American Mathematical Society
