🌙

对称拟定矩阵

Symmetric Quasidefinite Matrices

SIAM Journal on Optimization · 1995
被引 47
ABS 3

中文导读

定义了对称拟定矩阵,证明其任意对称置换可做LDL^T分解,并用于内点法中求解对称不定系统,比Bunch-Parlett分解更高效。

Abstract

It is stated here that a symmetric matrix K is quasidefinite if it has the form \[ K = \begin{bmatrix} - E & A^T \\ A & F \end{bmatrix}, \] where E and F are symmetric positive definite matrices. Although such matrices are indefinite, it is shown that any symmetric permutation of a quasidefinite matrix yields a factorization $LDL^T $. This result is applied to obtain a new approach for solving the symmetric indefinite systems arising in interior-point methods for linear and quadratic programming. These systems are typically solved either by reducing to a positive definite system or by performing a Bunch–Parlett factorization of the full indefinite system at every iteration. This is an intermediate approach based on reducing to a quasidefinite system. This approach entails less fill-in than further reducing to a positive definite system, but is based on a static ordering and is therefore more efficient than performing Bunch–Parlett factorizations of the original indefinite system.

线性代数矩阵分解内点法线性规划二次规划