A QMR-based interior-point algorithm for solving linear programs
R.W. Freund and F. Jarre
A new approach for the implementation of interior-point methods for
solving linear programs is proposed. Its main feature is the
iterative solution of the symmetric, but highly indefinite $2 \times
2$-block systems of linear equations that arise within the
interior-point algorithm. These linear systems are solved by a
symmetric variant of the quasi-minimal residual (QMR) algorithm, which
is an iterative solver for general linear systems. The symmetric QMR
algorithm can be combined with indefinite preconditioners, which is
crucial for the efficient solution of highly indefinite linear
systems, yet it still fully exploits the symmetry of the linear
systems to be solved. To support the use of the symmetric QMR
iteration, a novel stable reduction of the original unsymmetric
$3 \times 3$-block systems to symmetric $2 \times 2$-block systems is
introduced, and a measure for a low relative accuracy for the solution
of these linear systems within the interior-point algorithm is
proposed. Some indefinite preconditioners are discussed. Finally, we
report results of a few preliminary numerical experiments to
illustrate the features of the new approach.
AT&T Numerical Analysis Manuscript No. 94-19,
Bell Laboratories, Murray Hill, New Jersey, December 1994.