SIGNIFICANCE AND EXPLANATION

An iterative scheme is given for solving the linear complementarity problem x> 0, Mx + q> 0, xT(Mx + q) = 0. At each iteration the main effort is to find a point x satisfying x> 0, Mx + q 0 and a (scalar) linear inequality which is easily updated iteratively. It is shown that if M is a P-matrix or positive semidefinite, or satisfies a fairly weak positivity assumption, then the scheme converges to a solution. The scheme allows many possible implementations including sparsity-preserving methods and direct pivoting methods. An iterative linear programming method, LCP-ILP, is discussed in detail. The method is very similar to the Two-Phase method of linear programming. Numerical results are presented which indicate that LCP-ILP is more effective than Lemke's method in solving general linear complementarity problems