On the sparsity issues of interior point methods for quadratic programming

Csaba Meszaros

In this paper we will investigate how the sparsity of non-separable quadratic programming problems behaves in interior point methods. We will show that for the normal equation approach, two orderings can be performed in independent steps to reduce the fill-in during interior point iterations. One of the permutations has to be performed on the columns, whereas the other on the rows of the problem. We show that one can easily attribute the sparsity issues of non-separable quadratic programming problems to that of linear programming for which well--developed techniques are available. We describe how the fundamental structural properties of non--separable quadratic programming problems can be represented by a single matrix whose sparsity pattern can serve to determine the row permutation and to use heuristics developed for linear programming for determining which of the augmented system and normal equation approach is more advantageous. Numerical results are given on a wide variety of non--separable convex quadratic programming problems.

WP 98-4 Laboratory of Operations Research and Decision Systems, Hungarian Academy of Sciences

Contact: meszaros@sztaki.hu