Geometric Aspects of the Linear Complementarity Problem
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).
What people are saying - Write a review
We haven't found any reviews in the usual places.
THE CLASS OF UMATRICES
2 other sections not shown
1)-dimensional face affine hull associated assume bijective block pivoting boundary box list Chapter class of matrices column vectors common face complementary cone pos complementary cones containing constant parity property containing q contradiction convex convex cone copositive Corollary Cottle defined Definition degenerate complementary cone degenerate faces detMaa dim[pos dimensional dK(M example exists facet of K(M Figure full complementary cones full cone Hence hyperplane hyperspheres identity matrix implies index sets induction INS-matrices int pos C(a intersection LCP q Lemma Linear Complementarity Problem matrix classes nonnegative number of proper number of solutions open ball original LCP orthant P-matrices path pivoting on Maa point q principal minors principal transform proof of Theorem pseudomanifold q G int q is contained r-dimensional facet reduced LCP reflecting face regular Saigal semi-monotone sides of span sol(g solution to q span C(a).i strongly degenerate cones submatrix supporting hyperplane Suppose Theorem 2.6 zero