Least-Index Resolution of Degeneracy in Linear Complementarity Problems.

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, Lemke's algorithm, and Cottle's 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 Lemke's algorithm it must be at least three. Examples are given showing that these bounds are sharp. Finally, Murty's version of Bard's method is extended from P-matrices to the positive semi-definite case. (Author)

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 01, 1979
Accession Number
ADA080113

Entities

People

  • Yow-yieh Chang

Organizations

  • Stanford University

Tags

DTIC Thesaurus Topics

  • Algorithms
  • Coefficients
  • Computer Programming
  • Equations
  • Iterations
  • Linear Algebra
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • New York
  • Nonlinear Programming
  • Numbers
  • Operations Research
  • Quadratic Programming
  • Real Numbers
  • Sequences
  • Universities

Readers

  • Operations Research