Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2005-008 (August 04, 2005)

Sparse quasi-Newton updates with positive definite matrix completion
by Nobuo Yamashita

pdf File

The quasi-Newton method is a powerful method for solving unconstrained minimization problems. However, since the approximate Hessian generated by the usual quasi-Newton update (e.g. BFGS or DFP) becomes dense, the quasi-Newton method cannot be applied for large-scale problems due to lack of memory. To overcome this difficulty, we propose sparse quasi-Newton updates with positive definite matrix completion that exploit the sparsity pattern $E:=\{(i,j)\;|\; (\nabla^2 f(x))_{ij} \neq 0 \mbox{ for some }x\in R^n\}$ of the Hessian. The proposed method first calculates a partial approximate Hessian $H^{QN}_{ij}, (i,j) \in F$, where $F\supseteq E$, by using an existing quasi-Newton update formula such as BFGS or DFP. Next, we obtain a full matrix $H_{k+1}$, which is a maximum-determinant positive definite matrix completion of $H^{QN}_{ij}, (i,j) \in F$. If the sparsity pattern $E$ (or its extension $F$) has a property related to a chordal graph, then the matrix $H_{k+1}$ can be expressed as products of some sparse matrices. Therefore, if the Hessian is sparse, the time and space complexities of the proposed method are far fewer than those of the BFGS or the DFP. In particular, when the Hessian matrix is tridiagonal, the complexities become $O(n)$. We show that the proposed method has superlinear convergence under the usual assumptions.