##
A Polynomial Time Interior-Point Path Following Agorithm
for LCP Based on Chen-Harker-Kanzow Smoothing Techniques

###
Song Xu and Jim Burke

We establish a polynomial complexity bound for
an interior point path following algorithm for the monotone linear
complementarity problem that is based on the Chen--Harker--Kanzow
smoothing techniques. The fundamental difference
with the Chen--Harker and Kanzow algorithms is the introduction of
a rescaled Newton direction. The rescaling
requires the iterates to remain in the interior of the positive
orthant. To compensate for this restriction, the
iterates are not required to
remain feasible with respect to the affine constraints.
By staying in the interior of the positive orthant, we are able to
exploit the well developed convergence theory for interior point methods.
The convergence theory uses as a template
Tseng's simplified proof theory for infeasible interior point methods.
If the method is initiated at an interior point that is also
feasible with respect to the affine constraints, then the complexity
bound is O(\sqrt{n}L); otherwise, the complexity bound is O(nL).
Preliminary numerical experiments are
presented demonstrating that the new method is
extremely competitive not only with the Chen--Harker and Kanzow
non--interior methods but also with infeasible interior point strategies.
Preprint, Sept. 11, 1996, Math. Dept., Box 354350,
University of Washington, Seattle, WA 98195-4350

Contact: burke@math.washington.edu