A QMR-BASED INTERIOR-POINT ALGORITHM FOR SOLVING LINEAR-PROGRAMS

A new approach for the implementation of interior-point methods for so lving linear programs is proposed. Its main feature is the iterative s olution of the symmetric, but highly indefinite 2 x 2-block systems of linear equations that arise within the interior-point algorithm. Thes e linear systems are solved by a symmetric variant of the quasi-minima l residual (QMR) algorithm, which is an iterative solver for general l inear systems. The symmetric QMR algorithm can be combined with indefi nite preconditioners, which is crucial for the efficient solution of h ighly indefinite linear systems, yet it still fully exploits the symme try of the linear systems to be solved. To support the use of the symm etric QMR iteration, a novel stable reduction of the original unsymmet ric 3 x 3-block systems to symmetric 2 x 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 i ndefinite preconditioners are discussed. Finally, we report results of a few preliminary numerical experiments to illustrate the features of the new approach.