×

An optimal positive definite update for sparse Hessian matrices. (English) Zbl 0824.65038

The goal of the paper is to present a quasi-Newton update algorithm for smooth unconstrained optimization with the following properties:
1. A given sparsity pattern is preserved.
2. The quasi-Newton matrices remain positive definite.
3. A minimal change property is guaranteed.
4. The update reduces to the BFGS-formula in the dense case.
First a variational result based on the measure function \(\text{trace} (A) - \ln (\text{det}(A))\) is extended with respect to sparsity patterns to characterize a minimal update. Under the additional assumption that the sparsity pattern is not changed during an \(LDL\) factorization, formulas for the factor matrices \(L\) and \(D\) are derived. It is shown, that the solution of the variational problem is positive definite and uniquely determined by pattern elements of its inverse.
In the subsequent sections an iterative procedure is derived to compute the new update in a reliable and efficient way, since a special system of nonlinear equations must be solved in this case to preserve pattern information. Some numerical results for tridiagonal Hessians and the extended Rosenbrock function are presented. The new algorithm is compared with full BFGS, Nocedal, PR-cg, Newton and Lancelot methods. Finally some alternatives concerning primal methods to solve the variational problem and numerical stability questions are discussed.

MSC:

65K05 Numerical mathematical programming methods
90C30 Nonlinear programming
90C06 Large-scale problems in mathematical programming

Software:

LANCELOT; L-BFGS; ve08
PDFBibTeX XMLCite
Full Text: DOI