Content deleted Content added
Citation bot (talk | contribs) Alter: journal, pages. Add: doi. Formatted dashes. | Use this bot. Report bugs. | Suggested by Abductive | #UCB_toolbar |
AdaHephais (talk | contribs) Add internal link Tags: Visual edit Mobile edit Mobile web edit Advanced mobile edit |
||
| (3 intermediate revisions by 2 users not shown) | |||
Line 2:
== 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>
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
==Notes==
Line 105:
== 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-1 |mr=1150683}}
* {{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|mr=1286455|s2cid=21476636}}
| |||