## 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