Optimization of unconstrained functions with sparse hessian matrices-newton-type methods |
| |
Authors: | Mukund N Thapa |
| |
Institution: | (1) Department of Operations Research, Stanford University, 94305 Stanford, CA, USA |
| |
Abstract: | Newton-type methods for unconstrained optimization problems have been very successful when coupled with a modified Cholesky
factorization to take into account the possible lack of positive-definiteness in the Hessian matrix. In this paper we discuss
the application of these method to large problems that have a sparse Hessian matrix whose sparsity is known a priori.
Quite often it is difficult, if not impossible, to obtain an analytic representation of the Hessian matrix. Determining the
Hessian matrix by the standard method of finite-differences is costly in terms of gradient evaluations for large problems.
Automatic procedures that reduce the number of gradient evaluations by exploiting sparsity are examined and a new procedure
is suggested.
Once a sparse approximation to the Hessian matrix has been obtained, there still remains the problem of solving a sparse linear
system of equations at each iteration. A modified Cholesky factorization can be used. However, many additional nonzeros (fill-in)
may be created in the factors, and storage problems may arise. One way of approaching this problem is to ignore fill-in in
a systematic manner. Such technique are calledpartial factorization schemes. Various existing partial factorization are analyzed and three new ones are developed.
The above algorithms were tested on a set of problems. The overall conclusions were that these methods perfom well in practice. |
| |
Keywords: | Newton-type Methods Exploiting Sparsity Finite Difference Schemes Partial Factorization Schemes Numerical Results |
本文献已被 SpringerLink 等数据库收录! |
|