Accession Number : ADA181498
Title : The Equivalence of Dantzig's Self-Dual Parametric Algorithm for Linear Programs to Lemke's Algorithm for Linear Complementarity Problems Applied to Linear Programs.
Descriptive Note : Technical rept.,
Corporate Author : STANFORD UNIV CA SYSTEMS OPTIMIZATION LAB
Personal Author(s) : Lustig,Irvin J
PDF Url : ADA181498
Report Date : May 1987
Pagination or Media Count : 26
Abstract : Dantzig has asserted that his self-dual parametric algorithm for solving a linear program is equivalent to Lemke's method for solving a linear complementary problem when the latter is applied to solve a linear program. This paper formally proves that Dantzig's assertion is correct--specifically that the point reached along the solution path after 2t iterations of Lemke's method is identical with the point reached after t iterations of Dantzig's method. Keywords: Linear programming; Lemke's method; Self dual parametric algorithm; Linear complementarity problems.
Descriptors : *LINEAR PROGRAMMING, ALGORITHMS, PARAMETRIC ANALYSIS, ITERATIONS, PATHS, SOLUTIONS(GENERAL)
Subject Categories : Operations Research
Distribution Statement : APPROVED FOR PUBLIC RELEASE