The Equivalence of Dantzig's Self-Dual Parametric Algorithm for Linear Programs to Lemke's Algorithm for Linear Complementarity Problems Applied to Linear Programs.

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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
May 01, 1987
Accession Number
ADA181498

Entities

People

  • Irvin J. Lustig

Organizations

  • Stanford University

Tags

Communities of Interest

  • C4I

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Computer Programming
  • Convex Programming
  • Equations
  • Evolutionary Algorithms
  • Heuristic Methods
  • Iterations
  • Linear Programming
  • Mathematical Programming
  • Military Research
  • Operations Research
  • Optimization
  • Simplex Method
  • Two Dimensional
  • United States

Fields of Study

  • Mathematics

Readers

  • Operations Research