Accession Number : ADA116287

Title :   Geometric Aspects of the Linear Complementarity Problem.

Descriptive Note : Technical rept.,

Corporate Author : STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB

Personal Author(s) : Stone,Richard E

PDF Url : ADA116287

Report Date : May 1981

Pagination or Media Count : 152

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)

Descriptors :   *Mathematics, *Nonlinear systems, *Inequalities, *Matrices(Mathematics), Mathematical programming, Matrix theory, Geometry, Linear algebra, Linear programming

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE