Geometric Aspects of the Linear Complementarity Problem.
Abstract
A large part of the study of the Linear Complementarity Problem (LCP) has been concerned with matrix classes. A classic result of Samelson, Thrall, and Wesler is that the real square matrices with positive principal minors (P-matrices) are exactly those matrices M for which the LCP (q,M) has a unique solution for all real vectors q. Taking this geometrical characterization of the P-matrices and weakening, in an appropriate manner, some of the conditions, we obtain and study other useful and broad matrix classes thus enhancing our understanding of the LCP. In Chapter 2, we consider a generalization of the P-matrices by defining the class U as all real square matrices M where, if for all vectors x within some open ball around the vector q the LCP (x,M) has a solution, then (q,M) has a unique solution. We develop a characterization of U along with more specialized conditions on a matrix for sufficiency or necessity of being in U. Chapter 3 is concerned with the introduction and characterization of the class INS. The class INS is a generalization of U gotten by requiring that the appropriate LCP's (q,M) have exactly k solutions, for some positive integer k depending only on M. Hence, U is exactly those matrices belonging to INS with k equal to one. Chapter 4 continues the study of the matrices in INS. The range of values for k, the set of q where (q,M) does not have k solutions, and the multiple partitioning structure of the complementary cones associated with the problem are central topics discussed. Chapter 5 discusses these new classes in light of known LCP theory, and reviews its better known matrix classes. Chapter 6 considers some problems which remain open. (author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1981
- Accession Number
- ADA116287
Entities
People
- Richard E. Stone
Organizations
- Stanford University