Lemke's Method

摘要

Let M be an nth order matrix and q and d be vectors, both of order n, and let v be a scalar variable. Then the linear complementarity problem, (LCP) (q + Vd,M) is defined to be: Determine a vector x is less than or = 0 such that w = Mx + q + vd is less than or = 0 and x sup T w = 0. It is shown that if M is nondegenerate, every solution of LCP (q + Vd,M) for all values of v lies on a graph where the solutions corresponding to nodes are degenerate and those corresponding to arcs are nondegenerate. Nodes are associated with particular values while arcs are associated with open intervals of v. Arcs emanating from a given node are shown to be determined by the solutions of two smaller LCPs involving Schur complements of M, and this enables inductive proofs to be constructed for standard results, establishing relationships between the number of solutions for two different values of v and, in the case where M is a P-matrix, uniqueness of the solutions. It is suggested that this technique may be extended to divide the q-space into a number of cells in an attempt to isolate solutions of LCP(q,M).