|
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(''Mq'', ''qM'') seeks vectors ''z'' and ''w'' which satisfy the following constraints:
* <math>w, z \geqslant 0,</math> (that is, each component of these two vectors is [[Sign (mathematics)|non-negative]])
* <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 each<math>w_i</math> pairand <math>\{w_i,z_i\}</math> can be positive.
* <math>w = Mz + q</math>
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(''Mq'', ''qM'')}} havehas a solution for every ''q'', then ''M'' is a [[Q-matrix]]. If ''M'' is such that {{math|LCP(''Mq'', ''qM'')}} have a unique solution for every ''q'', then ''M'' is a [[P-matrix]]. Both of these characterizations are sufficient and necessary.<ref>{{cite journalsfnp|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}}</ref>
The vector ''w'' is a [[slack variable]],<ref>{{citationsfnp|title=Convex Optimization of Power Systems|first=Joshua Adam|last=Taylor|publisher=Cambridge University Press|year=2015| isbn=9781107076877|page=172|urlp=[https://books.google.com/books?id=JBdoBgAAQBAJ&pg=PA172 172]}}.</ref> and so is generally discarded after ''z'' is found. As such, the problem can also be formulated as:
* <math>Mz+q \geqslant 0</math>
\end{cases}</math>
with ''v'' the Lagrange multipliers on the non-negativity constraints, ''λ'' the <!-- Lagrange -->multipliers on the inequality constraints, and ''s'' the slack variables for the inequality constraints. The fourth condition derives from the complementarity of each group of variables {{math|(''x'', ''s'')}} with its set of KKT vectors (optimal Lagrange multipliers) being {{math|(''v'', ''λ'')}}. In that case,
: <math>z = \begin{bmatrix} x \\ \lambda \end{bmatrix}, \qquad w = \begin{bmatrix} v \\ s \end{bmatrix}</math>
: <math> x = Q^{-1}(A^{T} {\lambda} - c)</math>
pre-multiplying the two sides by ''A'' and subtracting ''b'' we obtain:
: <math> A x - b = A Q^{-1}(A^{T} {\lambda} - c) -b \,</math>
: <math> s = (A Q^{-1} A^{T}) {\lambda} + (- A Q^{-1} c - b )\,</math>
Calling now
:<math>\begin{align}
M &:= (A Q^{-1} A^{T}) \\
Qq &:= (- A Q^{-1} c - b)
\end{align}</math>
we have an LCP, due to the relation of complementarity between the slack variables ''s'' and their Lagrange multipliers ''λ''. Once we solve it, we may obtain the value of ''x'' from ''λ'' through the first KKT condition.
Finally, it is also possible to handle additional equality constraints:
:<math>\begin{align}
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} \\
Qq &:= - \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>
:<math>\begin{bmatrix} x \\ \mu \end{bmatrix} = \begin{bmatrix} Q & A_{eq}^{T} \\ -A_{eq} & 0 \end{bmatrix}^{-1} \begin{bmatrix} A^T \lambda - c \\ -b_{eq} \end{bmatrix}</math>
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">{{harvtxtsfnp|Murty|1988}}</ref><ref name="CPS92">{{harvtxtsfnp|Cottle|Pang|Stone|1992}}</ref> LCP problems can be solved also by the [[criss-cross algorithm]],<ref>{{harvtxtsfnp|Fukuda|Namiki|1994}}</ref><ref>{{harvtxtsfnp|Fukuda|Terlaky|1997}}</ref><ref name="HRT">{{cite journalsfnp|first1=D.den |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 sfnp|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{{sfnp|den name="HRT"/><ref name="CIsufficient"/>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.<ref name="HRT"/><ref name="CIsufficient"/><ref>{{cite journalsfnp|den last1=Cottle Hertog| first1=R. W. Roos|authorlink1=Richard W. CottleTerlaky|last2=Pang1993}}{{sfnp|first2=J.-S.Csizmadia|last3=VenkateswaranIllés|first3=V.2006}}{{sfnp|title=Sufficient matrices and the linear complementarity problem Cottle|journal=Linear Algebra and its ApplicationsPang|volume=114–115Venkateswaran|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.{{sfnp|Todd|1985|}}{{sfnp|Terlaky|Zhang|1993}}{{sfnp|Björner|Las Vergnas|Sturmfels|White|1999}}
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|series=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|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 ==
*[[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 a 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—31–3| pages=369–395|series=Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997 | editorseditor=Thomas M. Liebling and |editor2=Dominique de Werra |publisher=North-Holland Publishing Co. | ___location=Amsterdam |year=1997 |doi=10.1007/BF02614325|mr=1464775 | refciteseerx= harv10.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|refdoi-access=harv|format=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|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|editors=Thomas M. Liebling and Dominique de Werra|publisher=North-Holland Publishing Co. | ___location=Amsterdam |year=1997|doi=10.1007/BF02614325|mr=1464775|ref=harv|id=[http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps Postscript preprint]}}
▲* {{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}}
*{{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 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 web | url=http://www.utdallas.edu/~chandra/documents/6311/bimatrix.pdf | title=Bimatrix games | accessdate=18 December 2015 | author=R. Chandrasekaran | pages=5-7}} ▼* {{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|series=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|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-75–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|series=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|citeseerx=10.1.1.36.7658 |publisher=Springer Netherlands|issn=0254-5330|ref=harv}}
== External links ==
| 