Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
5-1-1984
Abstract
For the Linear Complementarity Problem (LCP) we have developed a finite descent algorithm that is capable of obtaining an optimal solution when the given matrix is a P-matrix. Conventional finite descent algorithms for solving geometric optimization problems move only from the current point to a geometrically adjacent one while traversing the feasible region. Here, we develop an algorithm that may 'jump' over infeasible regions during its operation. In a sense analogous to the methods of combinatorial optimization, the proposed algorithm exploits a 'nearness' structure that is defined not with respect to physical adjacency but with respect to the objective function and some constraint sets that are specified. In addition, we have developed a class of matrices for which, if our descent algorithm terminates without a solution, we can conclude that the LCP has no solution. The class consists of those matrices M whose inverse contains only nonpositive entries.
Keywords
Operations research, Linear complementarity problem, Linear programming, Mathematical optimization, Algorithms, Matrices
Publication Title
Dissertation/Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 541 ; 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
Venkateswaran, Venky, "A New Approach for Determining when the Linear Complementarity Problem has no Solution" (1984). Research Reports from the Department of Operations. 333.
https://commons.case.edu/wsom-ops-reports/333