Degeneracy Subgraph of the Lemke Complementary Pivot Algorithm and Anticycling Rule

S. R. Mohan
Additional contact information
S. R. Mohan: Delhi Centre

Journal of Optimization Theory and Applications, 1997, vol. 94, issue 2, No 7, 409-423

Abstract: Abstract In this paper, we use the theory of degeneracy graphs recently developed by Gal et al. to introduce a graph for studying the adjacency of almost complementary feasible bases, some of which may be degenerate, which are of interest in the context of the linear complementarity problem. We study the structure of this graph with particular reference to the possibility of cycling and various anticycling rules in the Lemke complementary pivoting algorithm. We consider the transition node pivot rule introduced by Geue and show that this rule helps in avoiding cycling in the Lemke complementary pivoting algorithm under a suitable assumption.

Keywords: Linear complementarity problem; degeneracy graph; cycling; transition node pivot rule (search for similar items in EconPapers)
Date: 1997
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1023/A:1022691830468 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:94:y:1997:i:2:d:10.1023_a:1022691830468

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1023/A:1022691830468

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().