# zbMATH — the first resource for mathematics

Symmetric indefinite systems for interior point methods. (English) Zbl 0791.90033
Summary: 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 $$\left[{-D^{-2}\atop A}{A^ T\atop 0}\right]$$ instead of reducing to obtain the usual $$AD^ 2 A^ T$$ system. This methodology affords two advantages: (1) it avoids the fill created by explicitly forming the product $$AD^ 2 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.

##### MSC:
 90C05 Linear programming 90C25 Convex programming 90C20 Quadratic programming 90-08 Computational methods for problems pertaining to operations research and mathematical programming
##### Software:
ALPO; MINOS; symrcm
Full Text: