Wikipedia

Linear complementarity problem: Difference between revisions

Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
Add internal link
Tags: Visual edit Mobile edit Mobile web edit Advanced mobile edit
 
(9 intermediate revisions by 5 users not shown)
Line 1:
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&nbsp;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, 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 <math>w_i</math> and <math>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(''q'', ''M'')}} havehas 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.<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|hdl=2027.42/34188|url=https://deepblue.lib.umich.edu/bitstream/2027.42/34188/1/0000477.pdf}}</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>
Line 91:
:<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&nbsp;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}}</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|s2cid=24418835 |url=http://www.cs.elte.hu/opres/orr/download/ORR03_1.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&nbsp;matrix]] is a generalization both of a [[positive-definite matrix]] and of a [[P-matrix]], whose [[principal&nbsp;minor]]s are each positive.<ref name="HRT"/><ref name="CIsufficient"/><ref>{{cite journalsfnp|den last1=Cottle Hertog| first1=R.&nbsp;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&nbsp;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 |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&nbsp;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 |s2cid=6058077|issn=0254-5330|ref=harv}}</ref><ref>{{cite book|last1=Björner|first1=Anders|last2=Las&nbsp;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|pages=417–479|doi=10.1017/CBO9780511586507|mr=1744046}}</ref>
 
== See also ==
Line 98:
*[[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 journal|last1=Cottle|first1=R. W.|authorlink1=Richard W. Cottle|last2=PangDantzig|first2=JG.-S B.|last3author-link2=Venkateswaran|first3=VG. B. Dantzig |title=SufficientComplementary matricespivot andtheory theof linearmathematical complementarityprogramming problem|journal=Linear Algebra and Its Applications |volume=114–1151 |datepages=March–April103–125 1989|pagesdate=231–2491968|doi=10.1016/0024-3795(8968)9046390052-19|mr=986877|refdoi-access=harvfree}}▼
* {{cite book|last1=Cottle|first1=Richard W.|last2=Pang|first2=Jong-Shi|last3=Stone|first3=Richard E. |title=The linear complementarity problem | series=Computer Science and Scientific Computing |publisher=Academic Press, Inc. |___location=Boston, MA|year=1992|pages=xxiv+762 pp|isbn=978-0-12-192350-1 |mr=1150683|ref=harv}}▼
* {{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|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}}▼
* {{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 |refciteseerx=harv10.1.1.36.9373 |s2cid=2794181 |id=[http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps Postscript preprint]|citeseerx=10.1.1.36.9373|s2cid=2794181}}▼
* {{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|refdoi-access=harvfree}}▼
* {{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 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-8 |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|archive-url-status=dead|archiveurl=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=dead}}▼
* {{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|last1=Terlaky|first1=Tamás <!-- authorlink1=Tamás Terlaky -->|last2=Zhang|first2=Shu&nbsp; 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 |s2cid=6058077|issn=0254-5330|ref=harv}}▼
*{{cite journal|last=Todd|first=Michael J.|author-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|ref=harv |doi-access=free}}▼
 
==Further reading==▼
▲* {{cite book|last1=Cottle|first1=Richard W.|last2=Pang|first2=Jong-Shi|last3=Stone|first3=Richard E.|title=The linear complementarity problem | series=Computer Science and Scientific Computing|publisher=Academic Press, Inc.|___location=Boston, MA|year=1992|pages=xxiv+762 pp|isbn=978-0-12-192350-1|mr=1150683|ref=harv}}
▲*{{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|mr=986877|ref=harv}}
▲* {{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 <!-- 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=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|ref=harv}}
▲* {{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-8|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|url-status=dead|archiveurl=https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|archive-date=2010-04-01}}
▲* {{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|ref=harv|id=[http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps Postscript preprint]|citeseerx=10.1.1.36.9373|s2cid=2794181}}
▲*{{cite journal|last=Todd|first=Michael J.|author-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|ref=harv|doi-access=free}}
*{{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}}
 
▲==Further reading==
* 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&nbsp;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 |s2cid=6058077|issn=0254-5330|ref=harv}}
 
== External links ==
Retrieved from "https://en.wikipedia.org/wiki/Linear_complementarity_problem"