Linear complementarity problem: Difference between revisions

Revision as of 23:47, 5 July 2021

Latest revision as of 08:09, 15 July 2025

(5 intermediate revisions by 4 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>

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.{{sfnp|Murty|1972}}

The vector ''w'' is a [[slack variable]],{{sfnp|Taylor|2015|p=[https://books.google.com/books?id=JBdoBgAAQBAJ&pg=PA172 172]}} and so is generally discarded after ''z'' is found. As such, the problem can also be formulated as:

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

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 itsIts Applications |volume=1 |pages=103-125103–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=free}}

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