Analysis of an Infeasible Interior Path-Following Method for Complementarity Problems

Paul Tseng

We study an infeasible interior path-following method for complementarity problems. The method uses a wide neighborhood and takes one or two Newton steps per iteration. We show that the method attains global convergence, assuming the iterates are defined and bounded (which occurs when the function is a $P_0$-$R_0$-function or when the function is monotone and a sufficiently positive solution exists). Moreover, the convergence rate is globally (respectively, locally) linear if the function is a uniformly $P$-function (respectively, at each cluster point, a certain submatrix of the Jacobian of the function is a $P$-matrix). By introducing an inexpensive active-set strategy in computing the second Newton direction, we show that the method attains local superlinear convergence without requiring the existence of a strictly complementary solution. The proof of this uses a local error bound on the distance from an iterate to a solution in terms of the square root of the centering parameter.

Report, Department of Mathematics, University of Washington, Seattle, August 1997 (revised September 1997).