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})\) from LCP(q, M) by adding some artificial variables and extra constraints, and show that the matrix \(\mathcal {M}_{1}\) belongs to the class of semimonotone matrices. However, LCP \((\bar{q}_{1},\mathcal {M}_{1})\) is not always solvable by Lemke’s algorithm. Then, we construct another artificial LCP \((\bar{q}_{2},\mathcal {M}_{2})\) from LCP \((\bar{q}_{1},\mathcal {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})\) 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}\) ) 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.
