A Least-Element Theory of Solving Linear Complementarity Problems as Linear Programs

Abstract
In a previous report (Cottle, R. W., J. S. Pang. 1978. On solving linear complementary problems as linear programs. Math. Programming Stud. 7 88–107.), the authors have established a least-element interpretation to Mangasarian's theory (Mangasarian, O. L. 1976. Linear complementarity problems solvable by a single linear program. Math. Programming 10 263–270; Mangasarian, O. L. 1975. Solution of linear complementarity problems by linear programming. In G. W. Watson, ed. Numerical Analysis, Dundée 1975. Lecture Notes in Mathematics, No. 506, Springer-Verlag, Berlin, 166–175.) of formulating some linear complementarity problems as linear programs. In the present report, we extend our previous analysis to a more general class of linear complementarity problems investigated in Mangasarian (Mangasarian, O. L. 1978. Characterization of linear complementarity problems as linear programs. Math. Programming Stud. 7 74–87.), Our purposes are (1) to demonstrate how solutions to these problems can be generated from least elements of polyhedral sets and (2) to investigate how these “least-element solutions” are related to the solutions obtained by the linear programming approach as proposed by Mangasarian.