Sparse quasi-Newton updates with positive definite matrix completion
成果类型：
Article
署名作者：
Yamashita, Nobuo
署名单位：
Kyoto University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-007-0137-1
发表日期：
2008
页码：
1-30
关键词：
摘要：
Quasi-Newton methods are powerful techniques for solving unconstrained minimization problems. Variable metric methods, which include the BFGS and DFP methods, generate dense positive definite approximations and, therefore, are not applicable to large-scale problems. To overcome this difficulty, a sparse quasi-Newton update with positive definite matrix completion that exploits the sparsity pattern E := {( i, j) vertical bar (del(2) f (x))(i j) not equal 0 for some x is an element of R-n} of the Hessian is proposed. The proposed method first calculates a partial approximate Hessian H-ij(QN), (i,j) is an element of F, where F superset of E, using an existing quasi-Newton update formula such as the BFGS or DFP methods. Next, a full matrix Hk+1, which is a maximum-determinant positive definite matrix completion of H-ij(QN), ( i, j) is an element of F, is obtained. If the sparsity pattern E (or its extension F) has a property related to a chordal graph, then the matrix Hk+1 can be expressed as products of some sparse matrices. The time and space requirements of the proposed method are lower than those of the BFGS or the DFP methods. In particular, when the Hessian matrix is tridiagonal, the complexities become O(n). The proposed method is shown to have superlinear convergence under the usual assumptions.