Linear complementarity problem: Difference between revisions

Revision as of 16:15, 17 November 2020

Revision as of 05:49, 25 November 2020

Line 8:

* <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'')}} have 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 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}}</ref>

The vector ''w'' is a [[slack variable]],<ref>{{citation|title=Convex Optimization of Power Systems|first=Joshua Adam|last=Taylor|publisher=Cambridge University Press|year=2015| isbn=9781107076877|page=172|url=https://books.google.com/books?id=JBdoBgAAQBAJ&pg=PA172}}.</ref> and so is generally discarded after ''z'' is found. As such, the problem can also be formulated as:

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">{{harvtxt|Murty|1988}}</ref><ref name="CPS92">{{harvtxt|Cottle|Pang|Stone|1992}}</ref> LCP problems can be solved also by the [[criss-cross algorithm]],<ref>{{harvtxt|Fukuda|Namiki|1994}}</ref><ref>{{harvtxt|Fukuda|Terlaky|1997}}</ref><ref name="HRT">{{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><ref name="CIsufficient">{{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 -->}}</ref> conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.<ref name="HRT"/><ref name="CIsufficient"/> 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 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 |mr=986877|ref=harv}}</ref>

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|lastlast1=Björner|firstfirst1=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 107:

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

Line 118:

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