Artículos de revistas
A robust and efficient proposal for solving linear systems arising in interior-point methods for linear programming
Registro en:
Computational Optimization And Applications. Springer, v. 56, n. 3, n. 573, n. 597, 2013.
0926-6003
1573-2894
WOS:000327240600005
10.1007/s10589-013-9572-5
Autor
Gonzalez-Lima, MD
Oliveira, ARL
Oliveira, DE
Institución
Resumen
Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) 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. 56 3 573 597 Universidad Simon Bolivar [GID-001 DID-USB] Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP) Universidad Simon Bolivar [GID-001 DID-USB]