Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
1-1-1986
Abstract
This research is concerned with the linear complementarity problem (LCP). In the first part of this research, we develop an algorithm which finds a solution to the LCP or detects that none exists when the given matrix M is either a P-matrix, or M is nonsingular and its inverse is nonpositive. Our approach is to solve an equivalent constrained optimization problem, the feasible region of which is the same as that defined by the linearity constraints of the LCP. The algorithm starts with a solution to the linearity constraints, if one exists, and solves a sequence of linear programming subproblems. All the subsequent points generated by our algorithm satisfy the linearity constraints. Under conditions on M as stated above, if the linearity constraints have a solution, then our algorithm finds a solution to the LCP, which then exists. We also provide a computational implementation of our algorithm, and computational results to compare our algorithm with that of Mangasarian's for the problems in which the given M-matrices are nonsingular and the inverses are nonpositive. As compared with Mangasarian's algorithm, although our algorithm takes lesser number of iterations, work per iteration needed in our algorithm is more. Thus, on average, our algorithm takes more time as compared with Mangasarian's algorithm. In addition, we show that the computational implementation of our algorithm is the same as that of Lemke's for the case in which M is a P-matrix. In the second part of this research we derive two major theoretical results on the LCP. First, we derive general and specific conditions on the M-matrix under which we can claim that the LCP has a closed-form solution. Second, we show the existence of an "associated" linear complementarity problem for any given LCP. We show that when an algorithm cannot process an LCP directly, it might be able to process the associated LCP, thereby indirectly processing the original LCP at the same time. This feature extends the capability of all the LCP algorithms. Numerical examples are given to illustrate the use of the associated LCP. Finally , we show how the associated LCP can be used to determine the class of matrices to which the given M-matrix belongs.
Keywords
Operations research, Linear complementarity problem, Algorithms, Mathematical optimization, Matrices, Linear programming, Numerical analysis
Publication Title
Dissertation, Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 569 ; Submitted in partial fulfillment of the requirements for the Degree of Doctor of Philosophy.
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Roy, Syamal, "A Sequential Linear Programming Approach for Solving the Linear Complementarity Problem" (1986). Research Reports from the Department of Operations. 510.
https://commons.case.edu/wsom-ops-reports/510