The Global Linear Convergence of an Infeasible Non-Interior Path-Following Algorithm for Complementarity Problems with Uniform P-Functions

Song Xu

We propose an infeasible non-interior path-following method for the nonlinear complementarity problems with uniform P-functions. This method is based on the smoothing techniques introduced by Kanzow. The key to our analysis is the introduction of a new notion of neighborhood for the central path which is suitable for infeasible non-interior path-following methods. By restricting the iterates in the neighborhood of the central path, we provide a natural rule to update the smoothing parameter and establish the global linear convergence of this method. Some preliminary computational results are reported.

Technical Report, Department of Mathematics, University of Washington, Seattle, WA 98195, December, 1996