In mathematical optimization, Lemke's algorithm is a procedure for solving linear complementarity problems, and more generally mixed linear complementarity problems.

Lemke's algorithm is of pivoting or basis-exchange type. Similar algorithms can compute Nash equilibria for two-person matrix and bimatrix games.

References

• Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). The linear complementarity problem. Computer Science and Scientific Computing. Boston, MA: Academic Press, Inc.. pp. xxiv+762 pp.. ISBN 0-12-192350-9.  MR1150683
• Murty, K. G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp.. ISBN 3-88538-403-5. http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/.  (Available for download at the website of Professor Katta G. Murty.) MR949214

External links

• OMatrix manual on Lemke
• Chris Hecker's GDC presentation on MLCPs and Lemke
• Linear Complementarity and Mathematical (Non-linear) Programming
• Siconos/Numerics open-source GPL implementation in C of Lemke's algorithm and other methods to solve LCPs amd MLCPs

Optimization: Algorithms, methods, and heuristics   Unconstrained nonlinear: Methods calling ... ... functions Golden section search · Interpolation methods · Line search · Successive parabolic interpolation ... and gradients Convergence Trust region · Wolfe conditions Quasi–Newton BFGS and L-BFGS · DFP · Symmetric rank-one (SR1) Other methods Gauss–Newton · Gradient · Levenberg–Marquardt · Conjugate gradient ... and Hessians Newton's method   Constrained nonlinear General Barrier methods · Penalty methods Differentiable Augmented Lagrangian methods · Sequential quadratic programming · Successive linear programming   Convex minimization General Interior point method · Reduced gradient (Frank–Wolfe) · Subgradient method · Cutting-plane method Linear and quadratic Interior point Ellipsoid method of Khachiyan · Projective algorithm of Karmarkar · Semidefinite programming Basis-exchange Simplex algorithm of Dantzig · Criss-cross algorithm · Principal pivoting algorithm of Lemke   Combinatorial Paradigms Approximation algorithm · Dynamic programming · Greedy algorithm · Integer programming (Branch & bound or cut) Graph algorithms Minimum spanning tree Bellman–Ford algorithm · Borůvka · Dijkstra · Floyd–Warshall  · Johnson · Kruskal Network flows Dinic · Edmonds–Karp · Ford–Fulkerson · Push-relabel maximum flow   Metaheuristics Evolutionary algorithm · Hill climbing · Local search · Simulated annealing · Tabu search Categories (Algorithms and methods · Heuristics) · Software