A QMR-based interior-point algorithm for solving linear programs |
| |
Authors: | Roland W Freund Florian Jarre |
| |
Institution: | 1. Bell Laboratories, 700 Mountain Avenue, Room 2C-420, 07 974-0636, Murray Hill, NJ, USA 2. Institut für Angewandte Mathematik und Statistik, Universit?t Würzburg, Am Hubland, D-97 074, Würzburg, Germany
|
| |
Abstract: | 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×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×3-block systems to symmetric 2×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. |
| |
Keywords: | Linear program Interior-point method Symmetric indefinite linear system Quasi-minimal residual iteration Indefinite preconditioner |
本文献已被 SpringerLink 等数据库收录! |
|