Symmetric indefinite systems for interior point methods

The authors present a unified framework for solving linear and convex quadratic programs via interior point methods. At each iteration, this method solves an indefinite system whose matrix is instead of reducing to obtain the usual system. This methodology affords two advantages: (1) it avoids the fill created by explicitly forming the product when A has dense columns; and (2) it can easily be used to solve nonseparable quadratic programs since it requires only that be symmetric. The authors also present a procedure for converting nonseparable quadratic programs to separable ones which yields computational savings when the matrix of quadratic coefficients is dense.