Fletcher, R. An optimal positive definite update for sparse Hessian matrices. (English) Zbl 0824.65038 SIAM J. Optim. 5, No. 1, 192-218 (1995). 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. Reviewer: K.Schittkowski (Bayreuth) Cited in 17 Documents MSC: 65K05 Numerical mathematical programming methods 90C30 Nonlinear programming 90C06 Large-scale problems in mathematical programming Keywords:sparse matrix update; BFGS method; Nocedal method; PR-cg method; Lancelot method; quasi-Newton update algorithm; smooth unconstrained optimization; BFGS-formula; \(LDL\) factorization; numerical results; tridiagonal Hessians; Rosenbrock function Software:LANCELOT; L-BFGS; ve08 PDFBibTeX XMLCite \textit{R. Fletcher}, SIAM J. Optim. 5, No. 1, 192--218 (1995; Zbl 0824.65038) Full Text: DOI