Simplified Characterizations of Linear Complementarity Problems Solvable as Linear Programs

Abstract
New and simplified characterizations are given for solving, as a linear program, the linear complementarity problem of finding an x in Rn such that Mx + q ≥ 0, x ≥ 0 and x1(Mx + q) = 0. The simplest such characterization given here is that if there exist n-dimensional vectors c, r, s which are nonnegative, and n-by-n matrices Z1, Z2, with nonpositive off-diagonal elements such that (i) MZ1 = Z2 + qcT and (ii) rTZ1 + sTZ2 > 0, then each solution of the linear program: Minimizex (rT + sT M)x subject to Mx + q ≥ 0, x ≥ 0, solves the linear complementarity problem. Conversely, if the linear complementarity problem has at least one vertex solution x which is nondegenerate. that is, x + Mx + q > 0, then there exist nonnegative vectors c, r, s and matrices Z1, Z2, with nonpositive off-diagonal elements, such that (i)–(ii) are satisfied.

This publication has 0 references indexed in Scilit: