On solving a larger subclass of linear complementarity problems by Lemke’s method

It is well known that the success of Lemke’s algorithm for solving a linear complementarity problem LCP(q, M) depends on the matrix class M. Many researchers investigated a large class of matrices for which Lemke’s algorithm computes a solution of the LCP(q, M). In this paper, we follow a different approach for the class of LCP, which is not solvable by Lemke’s algorithm. First, we construct an artificial LCP $$(\bar{q}_{1},\mathcal {M}_{1})$$ ( q ¯ 1 , M 1 ) from LCP(q, M) by adding some artificial variables and extra constraints, and show that the matrix $$\mathcal {M}_{1}$$ M 1 belongs to the class of semimonotone matrices. However, LCP $$(\bar{q}_{1},\mathcal {M}_{1})$$ ( q ¯ 1 , M 1 ) is not always solvable by Lemke’s algorithm. Then, we construct another artificial LCP $$(\bar{q}_{2},\mathcal {M}_{2})$$ ( q ¯ 2 , M 2 ) from LCP $$(\bar{q}_{1},\mathcal {M}_{1})$$ ( q ¯ 1 , M 1 ) by adding some more artificial variables and extra constraints that satisfy Eaves condition. We show that the resulting artificial LCP $$(\bar{q}_{2},\mathcal {M}_{2})$$ ( q ¯ 2 , M 2 ) is solvable by Lemke’s algorithm. Given an LCP(q, M), its solution can be obtained from the solution of the constructed artificial LCP( $$\bar{q}_{2},\mathcal {M}_{2}$$ q ¯ 2 , M 2 ) with Eaves conditions. This approach leads to an innovative scheme for solving a large class of LCPs which are not solvable by Lemke’s algorithm. Further, we also provide convergence results. The results obtained here can be used for broader applications of Lemke’s algorithm.