zbMATH — the first resource for mathematics

Optimization of unconstrained functions with sparse Hessian matrices - Newton-type methods. (English) Zbl 0538.49023
The author discusses Newton-type methods for unconstrained optimization problems with sparse Hessian. A finite-difference approximation to the Hessian matrix that reduces the number of gradient evaluations by exploiting sparsity and symmetry is presented. For solving the sparse linear system three partial factorization schemes are developed by taking a modified Cholesky-factorization and rejecting fill-in at some entries under certain conditions in order to avoid storage problems. The algorithms were tested on a set of problems. The overall conclusions were that these methods perform well in practice.
Reviewer: W.Zulehner

49M15 Newton-type methods
65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
49M37 Numerical methods based on nonlinear programming
Full Text: DOI
[1] T.F. Coleman and J.J. More, ”Estimation of sparse Jacobian matrices and graph coloring problems”,SIAM Journal of Numerical Analysis 20 (1983) 187–209. · Zbl 0527.65033
[2] A.R. Curtis, M.J.D. Powell and J.K. Reid, ”On the estimation of sparse Jacobian matrices”Journal of Institute for Mathematics and Its Applications 13 (1974) 117–119. · Zbl 0273.65036
[3] R.S. Dembo, S.C. Eisenstat and T. Steihaung, ”Inexact Newton Methods”,SIAM Journal of Numerical Analysis 19 (1982) 400–408. · Zbl 0478.65030
[4] P.E. Gill and W. Murray, ”The numerical solution of a problem in the calculus of variations”, in: D.J. Bell, ed.,Recent mathematical developments in control (Academic Press, London and New York, (1973) pp. 97–122.
[5] P.E. Gill and W. Murray, ”Newton-type methods for unconstrained and linearly constrained optimization”,Mathematical Programming 28 (1974) 311–350. · Zbl 0297.90082
[6] P.E. Gill and W. Murray, ”Performance evaluation for nonlinear optimization”, in L. Fosdick, ed.,Performance evaluation for numerical software (North-Holland, Amsterdam, 1979a) pp. 221–234.
[7] P.E. Gill and W. Murray, ”Conjugate-gradient methods for large-scale nonlinear optimization”, Technical Report SOL 79-15, Department of Operations Research, Stanford University, (Stanford, CA, 1979b).
[8] P.E. Gill, W. Murray and M.H. Wright,Practical optimization (Academic Press, London and New York, 1981). · Zbl 0503.90062
[9] P.E. Gill, W. Murray, M.A. Saunders and M.H. Wright, ”Two step-length algorithms for numerical optimization”, Technical Report SOL 79-25, Department of Operations Research, Stanford University (Stanford, CA, 1979).
[10] P. E. Gill, W. Murray and S.M. Picken, ”The implementation of two modified Newton algorithms for unconstrained optimization”, Technical Report NAC 11, National Physical Laboratory (England, 1972).
[11] I. Gustafsson, ”A class of first order factorization methods”,BIT 18 (1978) 142–156. · Zbl 0386.65006
[12] A. Jennings and G.M., Malik, ”Partial eliminations”,Journal of Institute for Mathematics and Its Applications 20 (1977) 307–316. · Zbl 0367.65019
[13] T.A. Manteuffel, ”An incomplete factorization technique for positive definite linear systems”,Mathematics of Computation 34 (1980) 473–497. · Zbl 0422.65018
[14] S.T. McCormick, ”Optimal approximation of sparse Hessians and its equivalence to a graph coloring problem”,Mathematical Programming 26 (1983) 153–171. · Zbl 0507.65027
[15] J.A. Meijerink and H.A. Van der Vorst, ”An iterative solution method for linear systems of which the coefficient matrix is a symmetricM-matrix”,Mathematics of Computation 31 (1977) 148–162. · Zbl 0349.65020
[16] N. Munksgaard, ”Solving sparse symmetric sets of linear equations by preconditioned conjugate gradients”,ACM Transactions on Mathematical Software 6 (1980) 206–219. · Zbl 0438.65035
[17] J.M. Ortega and W.C. Rheinboldt,Iterative solution of nonlinear equations in several variables (Academic Press, London and New York, 1970). · Zbl 0241.65046
[18] M.J.D. Powell and Ph.J. Toint, ”On the estimation of sparse Hessian matrices”,SIAM Journal of Numerical Analysis 16 (1979) 1060–1073. · Zbl 0426.65025
[19] H.H. Rosenbrock, ”An automatic method for finding the greatest or least value of a function”,The Computer Journal 3 (1960) 175–184.
[20] D.C. Sorensen, ”Newton’s method with a trust region modification”,SIAM Journal of Numerical Analysis 19 (1982) 409–426. · Zbl 0483.65039
[21] T Steihaug, ”Quasi-Newton methods for large scale nonlinear problems”, Technical Report Series 49, School of Organization and Management, Yale University, New Haven, CT, 1980).
[22] M.N. Thapa, ”Optimization of unconstrained functions with sparse Hessian matrices”, Ph.D. Thesis, Department of Operations Research, Stanford University Stanford, CA, (1980).
[23] M.N. Thapa, ”Optimization of unconstrained functions with sparse Hessian matrices–Quasi-Newton methods”,Mathematical Programming 25 (1982) 158–182. · Zbl 0513.90072
[24] Ph.L. Toint, ”Some numerical results using a sparse matrix updating formula in unconstrained optimization”,Mathematics of Computation 32 (1978) 839–851. · Zbl 0381.65036
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.