In
mathematical optimization
Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criterion, from some set of available alternatives. It is generally divided into two subfi ...
, Lemke's algorithm is a
procedure
Procedure may refer to:
* Medical procedure
* Instructions or recipes, a set of commands that show how to achieve some result, such as to prepare or make something
* Procedure (business), specifying parts of a business process
* Standard operat ...
for solving
linear complementarity problem In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968.
...
s, and more generally
mixed linear complementarity problem
In mathematical optimization theory, the mixed linear complementarity problem, often abbreviated as MLCP or LMCP, is a generalization of the linear complementarity problem to include free variables
In mathematics, and in other disciplines in ...
s. It is named after
Carlton E. Lemke.
Lemke's algorithm is of
pivoting or
basis-
exchange
Exchange may refer to:
Physics
* Gas exchange is the movement of oxygen and carbon dioxide molecules from a region of higher concentration to a region of lower concentration. Places United States
* Exchange, Indiana, an unincorporated community
* ...
type. Similar algorithms can compute
Nash equilibria
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equ ...
for
two-person matrix and bimatrix games.
References
*
* (Available for download at the website of Professo
Katta G. Murty)
External links
Chris Hecker's GDC presentation on MLCPs and LemkeLinear Complementarity and Mathematical (Non-linear) Programming*
Siconos/Numerics open-source GPL implementation in C of Lemke's algorithm and other methods to solve LCPs and MLCPs
Optimization algorithms and methods
{{algorithm-stub