|
In mathematical [[optimization (mathematics)|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 [[George Dantzig|Dantzig]] {{nowrap|in 1968.<ref name="Murty88"/><ref name="CPS92"/><ref>R. W. {{sfnp|Murty|1988}}{{sfnp|Cottle and [[G. B. |Pang|Stone|1992}}{{sfnp|Cottle|Dantzig]]. Complementary pivot theory of mathematical programming. ''Linear Algebra and its Applications'', 1:103-125, |1968.</ref>}}
== Formulation ==
Given a [[Matrix (mathematics)|real matrix]] '''M''' and [[Vector space|vector]] '''q''', the linear complementarity problem LCP(''q'', ''M'') seeks vectors '''z''' and '''w''' which satisfy the following constraints:
* <math> {w } \ge 0, {z } \ gegeqslant 0 \,</math> (that is, each component of these two vectors is [[Sign (mathematics)|non-negative ]]) ▼* <math>{w} = {Mz} + {q} \,</math> ▼* <math>z^Tw = 0</math> or equivalently <math>\sum\nolimits_i w_i z_i = 0.</math> This is the [[Complementarity theory|complementarity]] condition, since it implies that, for all <math>i</math>, at most one of <math>w_i</math> and <math>z_i</math> can be positive.
▲* <math>{w} \ge 0, {z} \ge 0\,</math> (that is, each component of these two vectors is non-negative)
▲* <math> {w } = {Mz } + {q } \,</math>
* <math>{w}_i {z}_i = 0\,</math> for all i. (The [[Complementarity theory|complementarity]] condition)
A sufficient condition for existence and uniqueness of a solution to this problem is that '''M''' be [[Symmetric matrix|symmetric]] [[Positive-definite matrix|positive-definite]]. If ''M'' is such that {{math|LCP(''q'', ''M'')}} has a solution for every ''q'', then ''M'' is a [[Q-matrix]]. If ''M'' is such that {{math|LCP(''q'', ''M'')}} have a unique solution for every ''q'', then ''M'' is a [[P-matrix]]. Both of these characterizations are sufficient and necessary.{{sfnp|Murty|1972}}
The vector <math>{''w}\,</math>'' is a [[slack variable]],{{sfnp|Taylor|2015|p=[https://books.google.com/books?id=JBdoBgAAQBAJ&pg=PA172 172]}} and so is generally discarded after <math>{''z}\,</math>'' is found.{{Citation needed|date=March 2012}} As such, the problem can also be formulated as:
* <math>{Mz}+{q} \gegeqslant {0}\,</math>
* <math>{z} \gegeqslant {0}\,</math>
* <math>{z}^{\mathrm{T}}({Mz}+{q}) = 0\,</math> (the complementarity condition)
==Convex quadratic-minimization: Minimum conditions==
Finding a solution to the linear complementarity problem is associated with minimizing the quadratic function
: <math>f({z}) = {z}^{\mathrm{T}}({Mz}+{q})\,</math>
subject to the constraints
: <math>{Mz}+{q} \gegeqslant {0}\,</math>
: <math>{z} \gegeqslant {0}\,</math>
These constraints ensure that ''f'' is always non-negative. The minimum of ''f'' is 0 at '''z''' if and only if '''z''' solves the linear complementarity problem.
If '''M''' is [[Positive-definite matrix|positive definite]], any algorithm for solving (strictly) convex [[Quadratic programming|QPs]] can solve the LCP. Specially designed basis-exchange pivoting algorithms, such as [[Lemke's algorithm]] and a variant of the [[simplex algorithm|simplex algorithm of Dantzig]] have been used for decades. Besides having polynomial time complexity, interior-point methods are also effective in practice.
Also, a quadratic-programming problem stated as minimize <math>f({x})={c}^T{x}Tx+\fractfrac{1}{2}{ x}^T{ Qx}\,</math> subject to <math>{Ax} \geqgeqslant {b} \,</math> as well as <math>{x} \gegeqslant {0}\,</math> with ''Q'' symmetric
is the same as solving the LCP with
* :<math>{q} = \left[\begin{arraybmatrix}{ c}{c} \\ -{b} \end{arraybmatrix}, \right]qquad M = \,begin{bmatrix} Q & -A^T \\ A & 0 \end{bmatrix}</math>
* <math>{M} = \left[\begin{array}{cc} {Q} & -{A}^{T}\\ {A} & 0\end{array}\right]\,</math>
This is because the [[Karush–Kuhn–Tucker]] conditions of the QP problem can be written as:
:<math>\begin{cases}
* <math>{v} = {Q} {x} - {A}^{T} {\lambda} + {c}\,</math> ▼v = Q x - A^T {\lambda} + c \\
s = A x - b \\
x, {\lambda}, v, s \geqslant 0 \\
* <math>{x }^{T} { v } + {\lambda}^ {T }{ s } = {0 }\,</math>▼\end{cases}</math>
...beingwith <math> {''v } \,</math>'' the Lagrange multipliers on the non-negativity constraints, <math> {\lambda} \,</math>''λ'' the <!-- Lagrange -->multipliers on the inequality constraints, and <math> {''s } \,</math>'' the slack variables for the inequality constraints. The fourth condition derives from the complementarity of each group of variables {{math|( <math>{''x }'', {''s '')}} \,</math>) with its set of KKT vectors (optimal Lagrange multipliers) being {{math|( <math>{''v }'', {\lambda''λ'')}} \. In that case, </math>).▼* <math>{s} = {A} {x} - {b}\,</math>
*: <math>z = \begin{xbmatrix}, {x \\ \lambda}, \end{vbmatrix}, \qquad w = \begin{sbmatrix} v \ge\ s \end{0bmatrix}\,</math>
If the non-negativity constraint on the <math>{''x }\,</math>'' is relaxed, the dimensionality of the LCP problem can be reduced to the number of the inequalities, as long as <math>{''Q }\,</math>'' is non-singular (which is guaranteed if it is [[Positive-definite matrix|positive definite]]). The multipliers <math>{''v }\,</math>'' are no longer present, and the first KKT conditions can be rewritten as: ▼▲* <math>{x}^{T}{v} + {\lambda}^{T}{s} = {0}\,</math>
▲*: <math> {v} = {Q } {x } -= {A }^{T} {\lambda} +- {c }\,</math>
▲...being <math> {v} \,</math> the Lagrange multipliers on the non-negativity constraints,<math> {\lambda} \,</math> the <!-- Lagrange -->multipliers on the inequality constraints, and <math> {s} \,</math> the slack variables for the inequality constraints. The fourth condition derives from the complementarity of each group of variables (<math>{x}, {s}\,</math>) with its set of KKT vectors (optimal Lagrange multipliers) being (<math>{v}, {\lambda}\,</math>).
In that case,
: <math>{z} x = \left[\beginQ^{array-1}(A^{cT}{x}\\ {\lambda}\end{array}\right]\, - c)</math>
: <math>{w} = \left[\begin{array}{c}{v}\\ {s}\end{array}\right]\,</math>
pre-multiplying the two sides by <math>{''A }\,</math>'' and subtracting <math>{''b }\,</math>'' we obtain: ▼▲If the non-negativity constraint on the <math>{x}\,</math> is relaxed, the dimensionality of the LCP problem can be reduced to the number of the inequalities, as long as <math>{Q}\,</math> is non-singular (which is guaranteed if it is [[Positive-definite matrix|positive definite]]). The multipliers <math>{v}\,</math> are no longer present, and the first KKT conditions can be rewritten as:
*: <math>{Q} {A x} - b = {A Q^{-1}(A^{T} {\lambda} - {c}) -b \,</math>
The left side, due to the second KKT condition, is <math>{''s }\,</math>''. Substituting and reordering: ▼
: <math> {x}s = {(A Q}^{-1}({ A}^{T}) {\lambda} + (- A Q^{c-1} c - b )\,</math>
Calling now
▲pre-multiplying the two sides by <math>{A}\,</math> and subtracting <math>{b}\,</math> we obtain:
:<math>\begin{align}
: <math> {A} {x} - {b} = {A} {Q}^{-1}({A}^{T} {\lambda} - {c}) -{b} \,</math>
M &:= (A Q^{-1} A^{T}) \\
q &:= (- A Q^{-1} c - b)
\end{align}</math>
Calling now <math> {M} \,\overset{\underset{\mathrm{def}}{}}{=}\, ({A} {Q}^{-1} {A}^{T})\,</math> and <math> {q} \,\overset{\underset{\mathrm{def}}{}}{=}\, (- {A} {Q}^{-1} {c} - {b})\,</math> we have an LCP, due to the relation of complementarity between the slack variables <math>{''s }\,</math>'' and their Lagrange multipliers <math>{\lambda}\,</math>''λ''. Once we solve it, we may obtain the value of <math>{''x }\,</math>'' from <math>{\lambda}\,</math>''λ'' through the first KKT condition. ▼▲The left side, due to the second KKT condition, is <math>{s}\,</math>. Substituting and reordering:
: <math> {s} = ({A} {Q}^{-1} {A}^{T}) {\lambda} + (- {A} {Q}^{-1} {c} - {b} )\,</math>
▲Calling now <math> {M} \,\overset{\underset{\mathrm{def}}{}}{=}\, ({A} {Q}^{-1} {A}^{T})\,</math> and <math> {q} \,\overset{\underset{\mathrm{def}}{}}{=}\, (- {A} {Q}^{-1} {c} - {b})\,</math> we have an LCP, due to the relation of complementarity between the slack variables <math>{s}\,</math> and their Lagrange multipliers <math>{\lambda}\,</math>. Once we solve it, we may obtain the value of <math>{x}\,</math> from <math>{\lambda}\,</math> through the first KKT condition.
Finally, it is also possible to handle additional equality constraints:
: <math>{A}_A_{eq}{x} = {b}_b_{eq} \,</math>
This introduces a vector of Lagrange multipliers <math>{\mu}\,</math>''μ'', with the same dimension as <math>{b}_b_{eq}\,</math>.
It is easy to verify that the <math>{''M}\,</math>'' and <math>{q}\,</math>''Q'' for the LCP system <math> {s} = {M} {\lambda} + {q} \,Q</math> are now expressed as:
:<math>\begin{align}
: <math> {M} ~\overset{\underset{\mathrm{def}}{}}{=}~ \left(\left[\begin{array}{cc}{A} & {0}\end{array}\right] \left[\begin{array}{cc} {Q} & {A}_{eq}^{T}\\ -{A}_{eq} & {0}\end{array}\right]^{-1} \left[\begin{array}{cc}{A}^{T} \\ {0}\end{array}\right]\right)\,</math>
M &:= \begin{bmatrix} A & 0 \end{bmatrix} \begin{bmatrix} Q & A_{eq}^{T} \\ -A_{eq} & 0 \end{bmatrix}^{-1} \begin{bmatrix} A^T \\ 0 \end{bmatrix} \\
q &:= - \begin{bmatrix} A & 0 \end{bmatrix} \begin{bmatrix} Q & A_{eq}^{T} \\ -A_{eq} & 0 \end{bmatrix}^{-1} \begin{bmatrix} c \\ b_{eq} \end{bmatrix} - b
\end{align}</math>
From <math>{\lambda}\,</math>''λ'' we can now recover the values of both <math>{''x }\,</math>'' and the Lagrange multiplier of equalities <math>{\mu}\,</math>''μ'': ▼: <math> {q} ~\overset{\underset{\mathrm{def}}{}}{=}~ \left(- \left[\begin{array}{cc}{A} & {0}\end{array}\right] \left[\begin{array}{cc} {Q} & {A}_{eq}^{T}\\ -{A}_{eq} & {0}\end{array}\right]^{-1} \left[\begin{array}{c}{c}\\ {b}_{eq}\end{array}\right] - {b}\right)\,</math>
:<math> \left[\begin{ arraybmatrix} {c}{ x } \\ {\mu } \end{ arraybmatrix} \right] = \left[\begin{ array}{ccbmatrix} {Q } & {A}_A_{eq}^{T} \\ - {A}_A_{eq} & {0 } \end{ arraybmatrix} \right]^{-1} \left[\begin{ array}{cbmatrix} {A }^ {T }{ \lambda } - { c } \\ - {b}_b_{eq} \end{ arraybmatrix} \right] \,</math> ▼
▲From <math>{\lambda}\,</math> we can now recover the values of both <math>{x}\,</math> and the Lagrange multiplier of equalities <math>{\mu}\,</math>:
In fact, most QP solvers work on the LCP formulation, including the [[interior point method]], principal / complementarity pivoting, and [[active set]] methods.{{sfnp|Murty|1988}}{{sfnp|Cottle|Pang|Stone|1992}} LCP problems can be solved also by the [[criss-cross algorithm]],{{sfnp|Fukuda|Namiki|1994}}{{sfnp|Fukuda|Terlaky|1997}}{{sfnp|den Hertog|Roos|Terlaky|1993}}{{sfnp|Csizmadia|Illés|2006}} conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.{{sfnp|den Hertog|Roos|Terlaky|1993}}{{sfnp|Csizmadia|Illés|2006}} A [[sufficient matrix]] is a generalization both of a [[positive-definite matrix]] and of a [[P-matrix]], whose [[principal minor]]s are each positive.{{sfnp|den Hertog|Roos|Terlaky|1993}}{{sfnp|Csizmadia|Illés|2006}}{{sfnp|Cottle|Pang|Venkateswaran|1989}}
▲<math>\left[\begin{array}{c}{x}\\ {\mu}\end{array}\right] = \left[\begin{array}{cc} {Q} & {A}_{eq}^{T}\\ -{A}_{eq} & {0}\end{array}\right]^{-1} \left[\begin{array}{c} {A}^{T}{\lambda}-{c}\\-{b}_{eq}\end{array}\right] \,</math>
Such LCPs can be solved when they are formulated abstractly using [[oriented matroid|oriented-matroid]] theory.{{sfnp|Todd|1985|}}{{sfnp|Terlaky|Zhang|1993}}{{sfnp|Björner|Las Vergnas|Sturmfels|White|1999}}
In fact, most QP solvers work on the LCP formulation, including the [[interior point method]], principal / complementarity pivoting, and [[active set]] methods.<ref name="Murty88">{{harvtxt|Murty|1988}}</ref><ref name="CPS92">{{harvtxt|Cottle|Pang|Stone|1992}}</ref> LCP problems can be solved also by the [[criss-cross algorithm]],<ref>{{harvtxt|Fukuda|Namiki|1994}}</ref><ref>{{harvtxt|Fukuda|Terlaky|1997}}</ref><ref name="HRT">{{cite journal|first1=D. |last1=den Hertog|first2=C.|last2=Roos|first3=T.|last3=Terlaky|title=The linear complementarity problem, sufficient matrices, and the criss-cross method|journal=Linear Algebra and its Applications|volume=187|date=1 July 1993|pages=1–14|url=http://core.ac.uk/download/pdf/6714737.pdf|doi=10.1016/0024-3795(93)90124-7|format=pdf}}</ref><ref name="CIsufficient">{{cite journal|first1=Zsolt|last1=Csizmadia|first2=Tibor|last2=Illés|title=New criss-cross type algorithms for linear complementarity problems with sufficient matrices|journal=Optimization Methods and Software|volume=21|year=2006|number=2|pages=247–266|doi=10.1080/10556780500095009|
url=http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf|format=pdf|<!-- ref=harv -->}}</ref> conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.<ref name="HRT"/><ref name="CIsufficient"/> A [[sufficient matrix]] is a generalization both of a [[positive-definite matrix]] and of a [[P-matrix]], whose [[principal minor]]s are each positive.<ref name="HRT"/><ref name="CIsufficient"/><ref>{{cite journal|last1=Cottle|first1=R. W.|authorlink1=Richard W. Cottle|last2=Pang|first2=J.-S.|last3=Venkateswaran|first3=V.|title=Sufficient matrices and the linear complementarity problem|journal=Linear Algebra and its Applications|volume=114–115|date=March–April 1989|pages=231–249|doi=10.1016/0024-3795(89)90463-1|url=http://www.sciencedirect.com/science/article/pii/0024379589904631|mr=986877|ref=harv}}</ref>
Such LCPs can be solved when they are formulated abstractly using [[oriented matroid|oriented-matroid]] theory.<ref name="Todd" >{{harvtxt|Todd|1985|}}</ref><ref>{{harvtxt|Terlaky|Zhang|1993}}: {{cite journal|last1=Terlaky|first1=Tamás|<!-- authorlink1=Tamás Terlaky -->|last2=Zhang|first2=Shu Zhong|title=Pivot rules for linear programming: A Survey on recent theoretical developments|issue=Degeneracy in optimization problems|journal=Annals of Operations Research|volume=46–47|year=1993|issue=1|pages=203–233|doi=10.1007/BF02096264|mr=1260019|id= {{citeseerx|10.1.1.36.7658}} |publisher=Springer Netherlands|issn=0254-5330|ref=harv}}</ref><ref>{{cite book|last=Björner|first=Anders|last2=Las Vergnas|author2-link=Michel Las Vergnas|first2=Michel|last3=Sturmfels|first3=Bernd|authorlink3=Bernd Sturmfels|last4=White|first4=Neil|last5=Ziegler|first5=Günter|authorlink5=Günter M. Ziegler|title=Oriented Matroids|chapter=10 Linear programming|publisher=Cambridge University Press|year=1999|isbn=978-0-521-77750-6|url=http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511586507|pages=417–479|doi=10.1017/CBO9780511586507|MR=1744046}}</ref>
== See also ==
*[[Complementarity theory]]
*[[Physics engine]] Impulse/constraint type physics engines for games use this approach.
*[[Contact dynamics]] Contact dynamics with the nonsmooth approach.
*[[Bimatrix game]]s can be reduced to LCP.
==Notes==
{{Reflist|24em}}
== References ==
* {{cite book|last1=Björner|first1=Anders|author-link1=Anders Björner|last2=Las Vergnas|author-link2=Michel Las Vergnas|first2=Michel|last3=Sturmfels|first3=Bernd|author-link3=Bernd Sturmfels|last4=White|first4=Neil |author-link4=Neil White|last5=Ziegler |first5=Günter|author-link5=Günter M. Ziegler |year=1999 |title=Oriented Matroids|chapter=10 Linear programming |publisher=Cambridge University Press|isbn=978-0-521-77750-6 |pages=417–479 |doi=10.1017/CBO9780511586507 |mr=1744046}}
* {{cite bookjournal|last1=Cottle|first1=RichardR. W.|last2=PangDantzig|first2=Jong-ShiG. B.|last3=Stone|first3author-link2=RichardG. EB. Dantzig |title=TheComplementary linearpivot complementaritytheory problemof |mathematical seriesprogramming |journal=ComputerLinear ScienceAlgebra and ScientificIts Applications Computing|publishervolume=Academic Press,1 Inc.|___locationpages=Boston,103–125 MA|yeardate=19921968|pagesdoi=xxiv+762 pp10.|isbn=01016/0024-12-1923503795(68)90052-9|mr=1150683|refdoi-access=harvfree}}
* {{cite journalbook|last1=Cottle|first1=R. W.|authorlink1=Richard W. Cottle|last2=Pang|first2=J.Jong-S.Shi|last3=VenkateswaranStone|first3=VRichard E. |title=SufficientThe matriceslinear and the linear complementarity problem |journal series=LinearComputer AlgebraScience and itsScientific Computing Applications|volumepublisher=114–115Academic Press, Inc. |date___location=March–AprilBoston, 1989MA|year=1992|pages=231–249xxiv+762 pp|doiisbn=10.1016/0024978-3795(89)904630-12-192350-1|url=http://www.sciencedirect.com/science/article/pii/0024379589904631 |mr=986877|ref=harv1150683}}
* {{cite journal|last1=Cottle|first1=ZsoltR. W.|last1authorlink1=Richard W. Cottle|last2=CsizmadiaPang|first2=TiborJ.-S. |last2last3=IllésVenkateswaran|first3=V.|title=NewSufficient criss-crossmatrices type algorithmsand forthe linear complementarity problemsproblem with sufficient matrices|journal=OptimizationLinear MethodsAlgebra and SoftwareIts Applications|volume=21114–115|yeardate=2006|number=2March–April 1989|pages=247–266231–249 |doi=10.10801016/105567805000950090024-3795(89)90463-1|mr=986877|doi-access=}}
* {{cite journal|first1=Zsolt|last1=Csizmadia|first2=Tibor|last2=Illés|title=New criss-cross type algorithms for linear complementarity problems with sufficient matrices|journal=Optimization Methods and Software|volume=21 |year=2006|number=2|pages=247–266 |doi=10.1080/10556780500095009 |s2cid=24418835 |url=http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf}}
url=http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf|format=pdf |<!-- ref=harv -->}}
* {{cite journal|last1=Fukuda|first1=Komei|authorlink1=Komei Fukuda|last2=Namiki|first2=Makoto|title=On extremal behaviors of Murty's least index method|journal=Mathematical Programming|date=March 1994|pages=365–370|volume=64|issue=1|doi=10.1007/BF01582581|ref=harv|mr=1286455|s2cid=21476636}}
* {{cite journal|first1=Komei|last1=Fukuda <!-- authorlink1=Komei Fukuda -->|first2=Tamás|last2=Terlaky <!-- authorlink2=Tamás Terlaky -->|title=Criss-cross methods: A fresh view on pivot algorithms |journal=Mathematical Programming, Series B|volume=79|issue=1–3| pages=369–395|series=Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997 |editor=Thomas M. Liebling |editor2=Dominique de Werra |year=1997 |doi=10.1007/BF02614325|mr=1464775 |citeseerx=10.1.1.36.9373 |s2cid=2794181 |id=[http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps Postscript preprint]}}
* {{cite journal|first1=D. |last1=den Hertog|first2=C.|last2=Roos|first3=T.|last3=Terlaky|title=The linear complementarity problem, sufficient matrices, and the criss-cross method| journal=Linear Algebra and itsIts Applications |volume=187|date=1 July 1993|pages=1–14|url=http://core.ac.uk/download/pdf/6714737.pdf|doi=10.1016/0024-3795(93)90124-7|formatdoi-access=pdffree}}
* {{cite book|last=Murty|first=K. G.|title=Linear complementarity, linear and nonlinear programming|series=Sigma Series in Applied Mathematics|volume=3|publisher=Heldermann Verlag|___location=Berlin|year=1988|pages=xlviii+629 pp.|isbn=3-88538-403-5|url=http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/| mr=949214|id=[http://www-personal.umich.edu/~murty/ Updated and free PDF version at Katta G. Murty's website]|ref=harv}} ▼* {{cite journal|last1=Murty|first1=Katta G.|title=On the number of solutions to the complementarity problem and spanning properties of complementary cones|journal=Linear Algebra and Its Applications |date=January 1972 |volume=5 |issue=1|pages=65–108 |doi=10.1016/0024-3795(72)90019-5 |hdl=2027.42/34188 |url=https://deepblue.lib.umich.edu/bitstream/2027.42/34188/1/0000477.pdf|hdl-access=free }}
* {{cite journal|first1=Komei|last1=Fukuda|<!-- authorlink1=Komei Fukuda -->|first2=Tamás|last2=Terlaky|<!-- authorlink2=Tamás Terlaky -->|title=Criss-cross methods: A fresh view on pivot algorithms |doi=10.1007/BF02614325|journal=Mathematical Programming: Series B|volume=79
▲* {{cite book|last=Murty|first=K. G.|title=Linear complementarity, linear and nonlinear programming |series=Sigma Series in Applied Mathematics|volume=3|publisher=Heldermann Verlag|___location=Berlin|year=1988 |pages=xlviii+629 pp.|isbn= 978-3-88538-403- 58 |url=http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/ | |mr=949214|id=[http://www-personal.umich.edu/~murty/ Updated and free PDF version at Katta G. Murty's website]| refarchive-url=https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|archive-date=2010-04-01|url-status= harvdead}}
|issue=1—3|pages=369–395|issue=Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997|editors=Thomas M. Liebling and Dominique de Werra|publisher=North-Holland Publishing Co. |___location=Amsterdam|year=1997|doi=10.1016/S0025-5610(97)00062-2|mr=1464775|ref=harv|id=[http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps Postscript preprint]}}
* {{cite book|last=Taylor|first=Joshua Adam|year=2015|title=Convex Optimization of Power Systems |publisher=Cambridge University Press |isbn=9781107076877 |url=https://books.google.com/books?id=JBdoBgAAQBAJ}}
*{{cite journal|last=Todd|first=Michael J.|authorlink=Michael J. Todd (mathematician)|title=Linear and quadratic programming in oriented matroids|journal=Journal of Combinatorial Theory|series=Series B|volume=39|year=1985|issue=2|pages=105–133|mr=811116|doi=10.1016/0095-8956(85)90042-5|ref=harv}} ▼* {{cite journal|last1=Terlaky|first1=Tamás | <!-- authorlink1=Tamás Terlaky -->|last2=Zhang|first2=Shu Zhong |title=Pivot rules for linear programming: A Survey on recent theoretical developments| issueseries=Degeneracy in optimization problems|journal=Annals of Operations Research|volume=46–47|year=1993|issue=1|pages=203–233 |doi=10.1007/BF02096264|mr=1260019| id citeseerx= {{citeseerx|10.1.1.36.7658 }} | publishers2cid= Springer Netherlands6058077|issn=0254-5330 |ref=harv}} ▼▲*{{cite journal|last=Todd|first=Michael J.| authorlinkauthor-link=Michael J. Todd (mathematician)|title=Linear and quadratic programming in oriented matroids|journal=Journal of Combinatorial Theory|series=Series B |volume=39 |year=1985 |issue=2|pages=105–133|mr=811116|doi=10.1016/0095-8956(85)90042-5 | refdoi-access= harvfree}}
==Further reading==
*{{cite web | url=http://www.utdallas.edu/~chandra/documents/6311/bimatrix.pdf | title=Bimatrix games | accessdate=18 December 2015 | author=R. Chandrasekaran | pages=5–7}}
* R. W. Cottle and [[G. B. Dantzig]]. Complementary pivot theory of mathematical programming. ''Linear Algebra and its Applications'', 1:103-125, 1968.
▲* {{cite journal|last1=Terlaky|first1=Tamás|<!-- authorlink1=Tamás Terlaky -->|last2=Zhang|first2=Shu Zhong|title=Pivot rules for linear programming: A Survey on recent theoretical developments|issue=Degeneracy in optimization problems|journal=Annals of Operations Research|volume=46–47|year=1993|issue=1|pages=203–233|doi=10.1007/BF02096264|mr=1260019|id = {{citeseerx|10.1.1.36.7658}} |publisher=Springer Netherlands|issn=0254-5330|ref=harv}}
== External links ==
* [httphttps://web.archive.org/web/20041029022008/http://www.american.edu/econ/gaussres/optimize/quadprog.src LCPSolve] — A simple procedure in GAUSS to solve a linear complementarity problem
* [http://www.openopt.org/LCP LCPSolve.py] — A Python/NumPy implementation of LCPSolve is part of [[OpenOpt]] since its release 0.32
* [[Siconos]]/Numerics open-source GPL implementation in C of Lemke's algorithm and other methods to solve LCPs and MLCPs
| 