Studies in the Complementarity Problem.

Although LCP(q,M), where M is a general integer matrix, is NP-complete, LCPs corresponding to integer Z-matrices, positive definite and semi definite matrices are solvable in polynomial time. For problems of order n Lemke's algorithm and Murty's Bard type algorithm were shown to require 2('n) pivot steps to solve the very nicest class of LCPs in the worst case. In the same way, we construct a class of LCP(q,M), with M being a P-matrix and positive semi definite, and show that Van der Heyden's variable dimension algorithm and Cottle and Dantzig's principal pivot method both require 2('n)-1 pivot steps to solve these nice LCPs of order n in the worst case. By giving a geometric interpretation to Van der Heyden's method, it is shown that it is equivalent to the parametric version of Murty's Bard type algorithm. Using this, a rule to resolve degeneracy is deduced. In chapter 3 we consider some perturbations of the matrix M and establish the limiting behavior of the perturbed solution. In chapter 4 we extend Van Bokhoven's iterative method for solving LCPs with symmetric positive definite matrices to the nonsymmetric case, and to some nonlinear complementary problems. Finally in chapter 5 some open questions relative to the complexity of the linear complementary problem with P-matrices are discussed.PhDOperations researchUniversity of Michiganhttp://deepblue.lib.umich.edu/bitstream/2027.42/159182/1/8304492.pd