Sparse quasi-Newton updates with positive definite matrix completion
Sparse quasi-Newton updates with positive definite matrix completion
复制标题
DOI：
10.1007/s10107-007-0137-1
复制
发表时间：
2008-05
影响因子：
2.7
通讯作者：
N. Yamashita
中科院分区：
文献类型：
--
作者：
N. Yamashita
准牛顿方法是求解无约束最小化问题的有力技术。可变度量方法，包括BFGS和DFP方法，产生密集的正定近似，因此不适用于大规模问题。为了克服这一困难，提出了一种利用Hessian稀疏模式$$E :=\{(i, j)\;|\; (\nabla^2 f(x))_{ij} \neq 0\,{\rm for\,some}\, x \in R^n\}$$的具有正定矩阵补全的稀疏拟牛顿更新。该方法首先利用现有的准牛顿更新公式（如BFGS或DFP方法）计算出部分近似Hessian。然后，得到一个满矩阵hk +1，它是一个极大行列式正定矩阵补全。如果稀疏模式ne（或其扩展f）具有与弦图相关的性质，则矩阵hk +1可以表示为一些稀疏矩阵的乘积。该方法对时间和空间的要求低于BFGS和DFP方法。特别地，当Hessian矩阵是三对角矩阵时，复杂度变为eo (n)。在通常的假设条件下，该方法具有超线性收敛性。
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)\;|\; (\nabla^2 f(x))_{ij} \neq 0\,{\rm for\,some}\, x \in R^n\}$$ of the Hessian is proposed. The proposed method first calculates a partial approximate Hessian, where, using an existing quasi-Newton update formula such as the BFGS or DFP methods. Next, a full matrixHk+1, which is a maximum-determinant positive definite matrix completion of, is obtained. If the sparsity patternE(or its extensionF) has a property related to a chordal graph, then the matrixHk+1can 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 becomeO(n). The proposed method is shown to have superlinear convergence under the usual assumptions.