Adaptive Use of Iterative Methods in Predictor-Corrector Interior Point
Methods for Linear Programming
Adaptive Use of Iterative Methods in Predictor-Corrector Interior Point
Methods for Linear Programming
Loading...
Files
Publication or External Link
Date
1999-04-06
Authors
Wang, Weichung
O'Leary, Dianne P.
Advisor
Citation
DRUM DOI
Abstract
In this work we devise efficient algorithms for finding the search
directions for interior point methods applied to linear programming
problems. There are two innovations. The first is the use of updating of
preconditioners computed for previous barrier parameters. The second is an
adaptive automated procedure for determining whether to use a direct or
iterative solver, whether to reinitialize or update the preconditioner,
and how many updates to apply. These decisions are based on predictions of
the cost of using the different solvers to determine the next search
direction, given costs in determining earlier directions. We summarize
earlier results using a modified version of the OB1-R code of Lustig,
Marsten, and Shanno, and we present results from a predictor-corrector
code PCx modified to use adaptive iteration. If a direct method is
appropriate for the problem, then our procedure chooses it, but when an
iterative procedure is helpful, substantial gains in efficiency can be
obtained.
(Also cross-referenced as UMIACS-TR-99-21)