## 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).

Contact: tseng@math.washington.edu