The Linear Complementarity Problem

B. Curtis Eaves
Additional contact information
B. Curtis Eaves: University of California, Berkeley

Management Science, 1971, vol. 17, issue 9, 612-634

Abstract: This study centers on the task of efficiently finding a solution of the linear complementarity problem: Ix - My = q, x \ge 0, y \ge 0, x \perp y. The main results are: (1) It is shown that Lemke's algorithm will solve (or show no solution exists) the problem for M \in L where L is a class of matrices, which properly includes (i) certain copositive matrices, (ii) certain matrices with nonnegative principal minors, (iii) matrices for bimatrix games. (2) If M \in L, if the system Ix - My = q, x \ge 0, y \ge 0 is feasible and nondegenerate, then the corresponding linear complementarity problem has an odd number of solutions. If M \in L and q > 0 then the solution is unique. (3) If for some M and every q \ge 0 the problem has a unique solution then M \in L and the problem has a solution for every q. (4) If M has nonnegative principal minors and if the linear complementarity with M and q has a nondegenerate complementary solution then the solution is unique. (5) If y T My + y T q is bounded below on y \ge 0 then the linear complementarity problem with M and q has a solution and Lemke's algorithm can be used to find such a solution. If, in addition, the problem is nondegenerate, then it has an odd number of solutions. (6) A procedure based on Lemke's algorithm is developed which either computes stationary points for general quadratic programs or else shows that the program has no optimum. (7) If a quadratic program has an optimum and satisfies a nondegeneracy condition then there are an odd number of stationary points.

Date: 1971
References: Add references at CitEc
Citations: View citations in EconPapers (34)

Downloads: (external link)
http://dx.doi.org/10.1287/mnsc.17.9.612 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:ormnsc:v:17:y:1971:i:9:p:612-634

Access Statistics for this article

More articles in Management Science from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().