COWLES FOUNDATION FOR RESEARCH IN ECONOMICS
AT YALE UNIVERSITY

Box 208281
New Haven, CT 06520-8281

COWLES FOUNDATION DISCUSSION PAPER NO. 549

"An Application of the Khachian-Shor Algorithm
to a Class of Linear Complementary Problems"

Ilan Adler, Richard P. McLean and J. Scott Provan

1980

The recent ellipsoidal method for solving linear programs due to Khachian and Shor is shown to process linear complementarity problems with positive semidefinite matrix. Suitable modifications 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.