Research Reports from the Department of Operations
Document Type
Dissertation
Publication Date
1-26-1972
Abstract
Consider the linear complementarity problem given by system (1): w = Mx + q (1) w ≥ 0, x ≥ 0 (2) } (I) x'w = 0 (3) where w, x and q are vectors of dimension n and M is a matrix of order n x n. Any (x,w) satisfying conditions (1) and (2) is a feasible solution to system (1). Any (x,w) satisfying (1), (2) and (3) is a complementary feasible solution to system (1). The main results derived in this work are given below. 1) Let MZ - class (i.e. off diagonal elements non-positive). Then Lemke's algorithm (scheme 1) when applied to system (1) will either result in a complementary feasible solution or in the conclusion that no feasible solution exists to the system for the given vector q. 2) Let M belong to the Saigal's class (i.e. - M is in Z-class and there exists s x > 0 such that x'M≤0). If the system (1) has a feasible solution then it has a complementary feasible solution. 3) A new class of matrices is defined: ℳ = {M / z' M ≥ 0 implies z ≥ 0} with w = 0 if and only if z=0. Also this new class is not contained in any one of the known classes, namely, copositive plus, positive definite or semi definite, P-matrices, P'-class etc. 4) The class E of matrices has been defined as those matrices for which existence of a feasible solution for system (I) for any q implies the existence of a complementary feasible solution for that q. A characterization of the E class is given as: M∈E if and only if for each vector q for which a complementary feasible solution exists, a complementary feasible solution exists for all s ≥ E. 5) Based on the characterization given in (4), an algorithm for processing system (1) is developed for M∈E. The algorithm can also be applied for matrices arising in bimatrix game problem and q < 0.
Keywords
Operations research, Linear complementarity problem, Matrices, Mathematical optimization, Linear programming, Game theory--Mathematical models
Publication Title
Dissertation/Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 253 ; 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
Rao, Arza K., "On the Linear Complementarity Problem" (1972). Research Reports from the Department of Operations. 368.
https://commons.case.edu/wsom-ops-reports/368