Symmetric indefinite systems for interior point methods

We 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 {Mathematical expression} instead of reducing to obtain the usual AD²A^T system. This methodology affords two advantages: (1) it avoids the fill created by explicitly forming the product AD²A^T when A has dense columns; and (2) it can easily be used to solve nonseparable quadratic programs since it requires only that D be symmetric. We also present a procedure for converting nonseparable quadratic programs to separable ones which yields computational savings when the matrix of quadratic coefficients is dense.