Linear complementarity problem: Difference between revisions

Revision as of 17:33, 14 January 2019

Latest revision as of 08:09, 15 July 2025

(21 intermediate revisions by 11 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(''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 <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(''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>

Line 69:

:<math>\begin{align}

M &:= (A Q^{-1} A^{T}) \\

Qq &:= (- A Q^{-1} c - b)

\end{align}</math>

Line 84:

:<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>

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|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&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 |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&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 |publisher=Springer Netherlands|issn=0254-5330|ref=harv}}</ref><ref>{{cite book|last=Björner|first=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|url=http://ebooks.cambridge.org/ebook.jsf?bid=CBO9780511586507|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.|last2=Dantzig|first2=G. B.|author-link2=G. B. Dantzig |title=Complementary pivot theory of mathematical programming |journal=Linear Algebra and Its Applications |volume=1 |pages=103–125 |date=1968|doi=10.1016/0024-3795(68)90052-9|doi-access=free}}

* {{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-91 |mr=1150683|ref=harv}}

* {{cite journal|last1=Cottle|first1=R.&nbsp; W.|authorlink1=Richard W. Cottle|last2=Pang|first2=J.-S. |last3=Venkateswaran|first3=V.|title=Sufficient matrices and the linear&nbsp; complementarity problem |journal=Linear Algebra and itsIts 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|refdoi-access=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}}

* {{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&nbsp; 16th International Symposium on Mathematical Programming held in Lausanne,&nbsp; 1997 |editorseditor=Thomas&nbsp; M. Liebling and |editor2=Dominique de&nbsp; Werra|publisher=North-Holland Publishing&nbsp;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&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 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 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-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]|ref=harv|deadurl=yes|archiveurlarchive-url=https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|archivedatearchive-date=2010-04-01|dfurl-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 |publishers2cid=Springer Netherlands6058077|issn=0254-5330|ref=harv}}

*{{cite journal|last=Todd|first=Michael&nbsp; J.|authorlinkauthor-link=Michael J. Todd (mathematician)|title=Linear and quadratic programming in oriented matroids|journal=Journal of Combinatorial Theory|series=Series&nbsp; 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 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=0-12-192350-9|mr=1150683|ref=harv}}

*{{cite journal|last1=Cottle|first1=R.&nbsp;W.|authorlink1=Richard W. Cottle|last2=Pang|first2=J.-S.|last3=Venkateswaran|first3=V.|title=Sufficient matrices and the linear&nbsp;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}}

* {{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 -->}}

* {{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}}

* {{cite journal|first1=D. |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=harv|format=pdf}}

* {{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|deadurl=yes|archiveurl=https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|archivedate=2010-04-01|df=}}

* {{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&nbsp;16th International Symposium on Mathematical Programming held in Lausanne,&nbsp;1997|editors=Thomas&nbsp;M. Liebling and Dominique de&nbsp;Werra|publisher=North-Holland Publishing&nbsp;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 journal|last=Todd|first=Michael&nbsp;J.|authorlink=Michael J. Todd (mathematician)|title=Linear and quadratic programming in oriented matroids|journal=Journal of Combinatorial Theory|series=Series&nbsp;B|volume=39|year=1985|issue=2|pages=105–133|mr=811116|doi=10.1016/0095-8956(85)90042-5|ref=harv}}

*{{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 |publisher=Springer Netherlands|issn=0254-5330|ref=harv}}

== External links ==