A Stable Iterative Method for Linear Programming
(with Maria Gonzalez-Lima, Universidad Simon Bolivar
and Hua Wei, University of Waterloo)
This paper studies a new
primal-dual interior/exterior-point method for linear programming.
We begin with the usual perturbed primal-dual optimality equations
$F_\mu(x,y,z)=0$. Under nondegeneracy
assumptions, this nonlinear system is well-posed,
i.e. it has a nonsingular Jacobian at optimality and is not necessarily
ill-conditioned as the iterates approach optimality.
We use a simple preprocessing step
to eliminate both the primal and dual feasibility
equations. This results in one single bilinear equation that
maintains the well-posedness property.
We then apply a preconditioned conjugate gradient method (PCG),
within an inexact Newton framework, directly on the
linearized equations. This is done
without forming the usual normal equations, NEQ, or
augmented system. Sparsity is maintained.
The work of an iteration consists almost entirely in
the (approximate) solution of this well-posed linearized system,
using PCG.
Therefore, improvements depend on efficient preconditioning.
Exact primal and dual feasibility are guaranteed throughout the
iterations when starting feasible.
Since the linearization is well posed,
standard preconditioners can be applied.
And we can use affine scaling and
not maintain positivity once we are close enough to the optimum,
i.e. we apply a crossover technique. This allows for warm
starts with perturbed data.
In addition, we correctly identify some of the primal and dual
variables that converge to 0 and delete them
(purify step). Therefore, we get
smaller systems as the iterations progress. These techniques reduce the
number and complexity of the iterations.
We present numerical examples where roundoff error causes problems for NEQ
and present numerical tests with direct solvers
as well as iterative solvers with both diagonal and
Cholesky type preconditioners.
Our tests show that our method takes direct advantage of sparsity and
stability of the data.
We include warm start tests for perturbed problems.