Please use this identifier to cite or link to this item: https://doi.org/10.1007/s10589-006-9006-8
Title: Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming
Authors: Chai, J.-S.
Toh, K.-C. 
Keywords: Inexact interior-point methods
Linear programming
Preconditioned iterative solver
Issue Date: Apr-2007
Citation: Chai, J.-S., Toh, K.-C. (2007-04). Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming. Computational Optimization and Applications 36 (2-3) : 221-247. ScholarBank@NUS Repository. https://doi.org/10.1007/s10589-006-9006-8
Abstract: We propose to compute the search direction at each interior-point iteration for a linear program via a reduced augmented system that typically has a much smaller dimension than the original augmented system. This reduced system is potentially less susceptible to the ill-conditioning effect of the elements in the (1,1) block of the augmented matrix. Apreconditioner is then designed by approximating the block structure of the inverse of the transformed matrix to further improve the spectral properties of the transformed system. The resulting preconditioned system is likely to become better conditioned toward the end of the interior-point algorithm. Capitalizing on the special spectral properties of the transformed matrix, we further proposed a two-phase iterative algorithm that starts by solving the normal equations with PCG in each IPM iteration, and then switches to solve the preconditioned reduced augmented system with symmetric quasi-minimal residual (SQMR) method when it is advantageous to do so. The experimental results have demonstrated that our proposed method is competitive with direct methods in solving large-scale LP problems and a set of highly degenerate LP problems. © Springer Science+Business Media, LLC 2007.
Source Title: Computational Optimization and Applications
URI: http://scholarbank.nus.edu.sg/handle/10635/103964
ISSN: 09266003
DOI: 10.1007/s10589-006-9006-8
Appears in Collections:Staff Publications

Show full item record
Files in This Item:
There are no files associated with this item.

SCOPUSTM   
Citations

16
checked on Jul 14, 2018

WEB OF SCIENCETM
Citations

16
checked on Jun 19, 2018

Page view(s)

23
checked on Jun 8, 2018

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.