Symmetric Quasidefinite Matrices
Author:
- Robert J. VanderbeiRVRobert J. Vanderbei
- 1 February 1995
- journal article
- research article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 5 (1) , 100-113
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.
Keywords
This publication has 16 references indexed in Scilit:
- Newton Methods for Large-Scale Linear Equality-Constrained MinimizationSIAM Journal on Matrix Analysis and Applications, 1993
- Solving symmetric indefinite systems in an interior-point method for linear programmingMathematical Programming, 1993
- On Implementing Mehrotra’s Predictor–Corrector Interior-Point Method for Linear ProgrammingSIAM Journal on Optimization, 1992
- Preconditioners for Indefinite Systems Arising in OptimizationSIAM Journal on Matrix Analysis and Applications, 1992
- Computational experience with a primal-dual interior point method for linear programmingLinear Algebra and its Applications, 1991
- Limiting behavior of the affine scaling continuous trajectories for linear programming problemsMathematical Programming, 1991
- Implementation of a Dual Affine Interior Point Algorithm for Linear ProgrammingINFORMS Journal on Computing, 1989
- The AT&TKorbx® SystemAT&T Technical Journal, 1989
- Some stable methods for calculating inertia and solving symmetric linear systemsMathematics of Computation, 1977
- Direct Methods for Solving Symmetric Indefinite Systems of Linear EquationsSIAM Journal on Numerical Analysis, 1971