A SUPERLINEAR INFEASIBLE-INTERIOR-POINT AFFINE SCALING ALGORITHM FOR LCP

We present an infeasible-interior-point algorithm for monotone linear complementarity problems in which the search directions are affine sca ling directions and the step lengths are obtained from simple formulae that ensure both global and superlinear convergence. By choosing the value of a parameter in appropriate ways, polynomial complexity and co nvergence with Q-order up to (but not including) two can be achieved. The only assumption made to obtain the superlinear convergence is the existence of a solution satisfying strict complementarity.