Research Reports from the Department of Operations
Document Type
Report
Publication Date
1-1-1983
Abstract
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.
Keywords
Operations research, Linear complementarity problem, Mathematical optimization, Algorithms, Linear programming, Computational efficiency
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 521
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Paparrizos, Konstantinos, "A Finite Improvement Algorithm for the Linear Complementarity Problem" (1983). Research Reports from the Department of Operations. 208.
https://commons.case.edu/wsom-ops-reports/208