A robust and efficient proposal for solving linear systems arising in interior-point methods for linear programming

María Gonzalez-Lima (), Aurelio Oliveira () and Danilo Oliveira ()

Computational Optimization and Applications, 2013, vol. 56, issue 3, 573-597

Abstract: We introduce an efficient and robust proposal for solving linear systems arising at each iteration of primal-dual interior-point methods for linear programming. Our proposal is based on the stable system presented by Gonzalez-Lima et al. (Comput. Opt. Appl. 44:213–247, 2009 ). Using similar techniques as those employed in the splitting preconditioner introduced by Oliveira and Sorensen (Linear Algebra Appl. 394:1–24, 2005 ) we are able to express the stable system matrix in block form such that the diagonal blocks are nonsingular diagonal matrices and the off-diagonal blocks are matrices close to zero when the iterates are close to the solution set of the linear programming problem. For degenerate problems a perturbation of the diagonal is added. We use a low-cost fixed iterative method to solve this system. Numerical experiments have shown that our approach leads to very accurate solutions for the linear programming problem. Copyright Springer Science+Business Media New York 2013

Keywords: Linear programming; Primal-dual interior point methods; Linear systems (search for similar items in EconPapers)
Date: 2013
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1007/s10589-013-9572-5 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:56:y:2013:i:3:p:573-597

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-013-9572-5

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().