Solution of Linear Complementarity Problems by Linear Programming
Olvi Mangasarian
1975
The linear complementarity problem is that of finding an n x 1 vector z such that, Mz + q 2 0, z 2 0, z (Mz+q) = 0 where M is a given n x n real matrix and q is a given n x 1 vector. In this paper the class of matrices M for which this problem is solvable by a single linear program is enlarged to include matrices other than those that are Zmatrices or those that have an inverse which is a Zmatrix. (A Zmatrix is real square matrix with nonpositive offdiagonal elements.) Included in this class are other matrices such as nonnegative matrices with a strictly dominant diagonal and matrices that are the sum of a Zmatrix having a nonnegative inverse and the tensor product of any two positive vectors in R~.
Download this report (PDF)
Return to tech report index
