Thursday, April 18, 9:30 am in MTH 3206, University of Maryland,
College Park
Adaptive Use of Iterative Methods in Interior Point
Methods for Linear Programming
Prof. Dianne P. O'Leary
Computer Science Department and UMIACS,
University of Maryland
oleary@cs.umd.edu
This talk focusses on 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.
These ideas are tested by applying a modified version of the
OB1-R code of Lustig, Marsten, and Shanno to a variety of
problems from the NETLIB and other collections. 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. This is
joint work with Weichung Wang.
|