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

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. Programming10 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.