Linear Complementarity Problems Solvable by a Single Linear Program

Abstract

It is shown that the linear complementarity problem of finding a z in Rn such that Mz + q > 0, z > 0 and zT (Mz+q) = 0 can be solved by a single linear program in some important special cases such as when M or its inverse is a Z-matrix, that is a real square matrix with nonpositive off-diagonal elements. As a consequence certain problems in mechanics, certain problems of finding the least element of a polyhedral set and certain quadratic programing problems, can each be solved by a single linear program.