mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...

, Lemke's algorithm is a procedure 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 problems. It is named after Carlton E. Lemke. Lemke's algorithm is of pivoting or

basis Basis is a term used in mathematics, finance, science, and other contexts to refer to foundational concepts, valuation measures, or organizational names; here, it may refer to: Finance and accounting * Adjusted basis, the net cost of an asse ...

exchange Exchange or exchanged may refer to: Arts, entertainment and media Film and television * Exchange (film), or ''Deep Trap'', 2015 South Korean psychological thriller * Exchanged (film), 2019 Peruvian fantasy comedy * Exchange (TV program), 2021 Sou ...

type. Similar algorithms can compute

Nash equilibria In game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed) ...

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 Lemke

Linear Complementarity and Mathematical (Non-linear) Programming
*

Siconos SICONOS is an open source scientific software primarily targeted at modeling and simulating non-smooth dynamical systems (NSDS): * Mechanical systems (Rigid body or solid) with Unilateral contact and Coulomb friction as we find in Non-smooth mec ...

/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