A Superlinear Infeasible-Interior-Point Algorithm for Monotone Complementarity Problems

We use the globally convergent framework proposed by Kojima, Noma, and Yoshise to construct an infeasible-interior-point algorithm for monotone nonlinear complementarity problems. Superlinear convergence is attained when the solution is nondegenerate and also when the problem is linear. Numerical experiments confirm the efficacy of the proposed approach. 1 Introduction We consider the problem of finding a vector pair (x; y) 2 IR n \Theta IR n such that y = f(x); (x; y) 0; x T y = 0; (1) where f : IR n ! IR n is continuously differentiable in an open set containing the nonnegative orthant of IR n (denoted by IR n + ) and monotone, that is, (x 0 \Gamma x) T (f(x 0 ) \Gamma f(x)) 0 for all x 0 ; x 2 IR n + : Problem (1) is a monotone nonlinear complementarity problem, abbreviated as NCP. We use S to denote the solution set for (1). Interior-point algorithms for problems of this type have been considered recently by Kojima, Noma, and Yoshise [4], Guler [3], an..