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