Accession Number:

ADA080113

Title:

Least-Index Resolution of Degeneracy in Linear Complementarity Problems.

Descriptive Note:

Technical rept.,

Corporate Author:

STANFORD UNIV CA DEPT OF OPERATIONS RESEARCH

Personal Author(s):

Report Date:

1979-10-01

Pagination or Media Count:

57.0

Abstract:

This study centers on the circling phenomenon associated with degeneracy in linear complementarity problems and presents an easily implemented technique for resolving it. With certain exceptions, the device is to use the least-index for selecting the variable to leave the basic set. The results of this report pertain only to linear complementarity problems involving P-matrices or positive semi-definite matrices. With this restriction, it is shown that inclusion of the least-index pivot selection rule insures finiteness for the principal pivoting method of Dantzig and Cottle, Lemkes algorithm, and Cottles parametric principal pivoting method. It is shown that for circling to occur in the principal pivoting method, the matrix must have order at least four, and for Lemkes algorithm it must be at least three. Examples are given showing that these bounds are sharp. Finally, Murtys version of Bards method is extended from P-matrices to the positive semi-definite case. Author

Subject Categories:

  • Theoretical Mathematics
  • Operations Research

Distribution Statement:

APPROVED FOR PUBLIC RELEASE