CLASS OF COMPLEMENTARY CONES AND LEMKES ALGORITHM

A geometrical description of Lemke's algorithm is presented for solving the linear complementarity problem. A study is made of the class of all complementary cones and it is shown that, under a regularity condition on this class, necessary and sufficient conditions for the success of Lemke's algorithm can be proved. It is also shown that this regularity condition is satisfied by some known classes of complementary cones. A class of matrices for which all principal minors are negative is added to the existing classes of matrices for which the linear complementarity problem can be solved by Lemke's algorithm.