A finite improvement algorithm for the linear complementarity problem

This research is concerned with the development of a computationally efficient improvement algorithm for the linear complementarity problem (LCP). Our approach to finding a solution to the 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. An optimal solution with objective function value of zero yields a solution of the LCP. The algorithm, descent 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 for our COP whose objective function (unlike the simplex method) changes in form throughout the computations. The current point is tested for optimality. If the point is not optimal, a search is made for an improving feasible direction. If successful, a modified min-ratio test determines the maximum amount of movement. It has been shown that when the LCP has a P-matrix, the algorithm terminates finitely with the unique solution of the LCP. The computational study showed that our algorithm is clearly superior to the previous improvement algorithm (of Sengupta). An improvement of about 50 percent in the number of iterations has been observed. This improvement tends to increase with the size of the problem. However, Lemke's well-known algorithm, which is not improving in nature, remains superior to ours. Our algorithm was better than Lemke's only for problems of small size.