A finite improvement algorithm for the Linear Complementarity Problem

This paper is concerned with the development of an improvement algorithm for the Linear Complementarity Problem (LCP). Our approach to find a solution to LCP is to solve the equivalent Constrained Optimization Problem (COP) of maximizing the sum of the minimum of each complementary pair of variables, subject to the constraints that each such minimum is nonpositive. The algorithm, ascent in nature, is similar to the simplex method in the sense that it moves between basic points of an associated system of linear equations. These basic points are feasible to our COP whose objective function is piecewise linear and concave. Classes of matrices are characterized for which our algorithm processes LCP for every right hand side vector and every matrix in the class. A computational study shows that our algorithm is clearly superior to a previous improvement algorithm. Computational comparisons with Lemke’s well known algorithm are also presented.