Preconditioning and iterative solution of symmetric indefinite linear systems arising from interior point methods for linear programming |
| |
Authors: | Joo-Siong Chai Kim-Chuan Toh |
| |
Institution: | (1) Computational Engineering Program, Singapore-MIT Alliance, 4 Engineering Drive 3, Singapore, 117576, Singapore;(2) Department of Mathematics, National University of Singapore, 2 Science Drive 2, Singapore, 117543, Singapore;(3) Singapore-MIT Alliance, E4-04-10, 4 Engineering Drive 3, Singapore, 117576, Singapore |
| |
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. A preconditioner 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.
Research supported in parts by NUS Research Grant R146-000-076-112 and SMA IUP Research Grant. |
| |
Keywords: | Linear programming Inexact interior-point methods Preconditioned iterative solver |
本文献已被 SpringerLink 等数据库收录! |
|