An Application of the KhachianShor Algorithm to a Class of Linear Complementary Problems
The recent ellipsoidal method for solving linear programs due to Khachian and Shor is shown to process linear complementarity problems with positive semideﬁnite matrix. Suitable modiﬁcations of all lemmas are presented and it is shown that the algorithm operates in polynomial time of the same order as that required for linear programming. Thus quadratic programming problems are solvable in polynomial time.
Adler, Ilan; McLean, Richard P.; and Provan, J. Scott, "An Application of the KhachianShor Algorithm to a Class of Linear Complementary Problems" (1980). Cowles Foundation Discussion Papers. 785.