A QMR-based interior-point algorithm for solving linear programs
Freund, Roland W.
Jarre, Florian

Data: 1997
Resum: 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.
Drets: Tots els drets reservats.
Llengua: Anglès
Document: Article ; recerca ; Versió publicada
Matèria: Linear program ; Interior-point method ; Symmetric indefinite linear system ; Quasi-minimal residual iteration ; Indefinite preconditioner
Publicat a: Mathematical Programming, vol. 76 n. 1 (1997) p. 183-210, ISSN 0025-5610

28 p, 1.4 MB
 Accés restringit a la UAB

El registre apareix a les col·leccions:
Articles > Articles de recerca
Articles > Articles publicats

 Registre creat el 2006-03-13, darrera modificació el 2023-06-03

   Favorit i Compartir