A new purification method for monotone linear complementarity problems

In this paper, we propose a new purification method for monotone linear complementarity problems. This method associates to each iterate of the sequence, generated by an interior point method, one basis which is not necessarily feasible. We show that, under the strict complementarity and non-degeneracy hypotheses, the sequence of bases converges on a finite number of iterations to an optimal basis which gives the exact solution of the problem. The adopted process also serves to precondition the conjugate gradient algorithm when computing the Newton direction.