A finite improvement algorithm for the linear complementarity problem (Q1823161)

The authors consider the linear complementarity problem (LCP) \[ Iw- Mz=q,\quad w\geq 0,\quad z\geq 0,\quad w^ Tz=0, \] where M is an \(n\times n\) real matrix, q is an n-dimensional real vector and I is the \(n\times n\) identity matrix. The authors present an algorithm similar to the simplex method in the sense that it moves between basic points of an associated system of linear equations. Computational comparisons are presented. Also, classes of matrices are characterized for which the algorithm processes LCP for every matrix M in the class and every vector q.