Linear complementarity problem: Difference between revisions

Revision as of 15:11, 15 August 2010

Latest revision as of 08:09, 15 July 2025

(107 intermediate revisions by 46 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]] in 1968.{{sfnp|Murty|1988}}{{sfnp|Cottle|Pang|Stone|1992}}{{sfnp|Cottle|Dantzig|1968}}

== 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>\mathbf{w} \ge 0, \mathbf{z} \gegeqslant 0,</math> (that is, each component of these two vectors is [[Sign (mathematics)|non-negative]])

* <math>\mathbf{w} = \mathbf{Mz} + \mathbf{q} </math>

* <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>\mathbf{w} \ge 0, \mathbf{z} \ge 0</math> (that is, each component of these two vectors is non-negative)

* <math>\mathbf{w} = \mathbf{Mz} + \mathbf{q} </math>

* <math>{w}_i {z}_i = 0</math> for all i. (The [[Complementarity theory |complementarity]] condition)

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'')}} has 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 <math>\mathbf{''w}</math>'' is a [[slack variable]],{{sfnp|Taylor|2015|p=[https://books.google.com/books?id=JBdoBgAAQBAJ&pg=PA172 172]}} and so is generally discarded after <math>\mathbf{''z}</math>'' is found. As such, the problem can also be formulated as:

* <math>\mathbf{Mz}+\mathbf{q} \gegeqslant \mathbf{0}</math>

* <math>\mathbf{z} \gegeqslant \mathbf{0}</math>

* <math>\mathbf{z}^{\mathrm{T}}(\mathbf{Mz}+\mathbf{q}) = 0</math> (the complementarity condition)

==Relation toConvex quadratic-minimization: Minimum programmingconditions==

According to the [[Karush–Kuhn–Tucker conditions]], findingFinding a solution to the linear complementarity problem is equivalentassociated towith minimizing the quadratic function

: <math>f(z) = z^T(Mz+q)</math>

According to the [[Karush–Kuhn–Tucker conditions]], finding a solution to the linear complementarity problem is equivalent to minimizing the quadratic function

: <math>f(\mathbf{z}) = \mathbf{z}^{\mathrm{T}}(\mathbf{Mz}+\mathbf{q})</math>

subject to the constraints

: <math>\mathbf{Mz}+\mathbf{q} \gegeqslant \mathbf{0}</math>

: <math>\mathbf{z} \gegeqslant \mathbf{0}</math>

Because theseThese constraints ensure that ''f'' is always non-negative,. it attains itsThe minimum of ''f'' is 0 at '''z''' if and only if '''z''' solves the linear complementarity problem.

If '''M''' is [[Positive-definite matrix|positive definite]], any algorithm for solving (convexstrictly) convex [[Quadratic programming|QPs]] can of course be used to solve the LCP. However,Specially theredesigned also exist more efficient,basis-exchange specializedpivoting algorithms, such as [[Lemke's algorithm]] and a variant of the [[Simplexsimplex algorithm | Dantzig'ssimplex algorithm of Dantzig]] have been used for decades. Besides having polynomial time complexity, interior-point methods are also effective in practice.

Also, a quadratic -programming problem stated as minimize <math>f(\mathbf{x})=\mathbf{c}^T\mathbf{x}Tx+\fractfrac{1}{2}\mathbf{ x}^T\mathbf{ Qx}</math> subject to <math>\mathbf{Ax} \geqgeqslant \mathbf{b}</math> as well as <math>x \geqslant 0</math> with ''Q'' symmetric

is the same as solving the LCP with

* :<math>\mathbf{q} = \left[\begin{arraybmatrix}{ c} \mathbf\ -b \end{cbmatrix}, \qquad M = \-\mathbfbegin{bbmatrix} Q & -A^T \\ A & 0 \end{arraybmatrix}\right]</math>

* <math>\mathbf{M} = \left[\begin{array}{cc} \mathbf{Q} & -\mathbf{A}^{T}\\ \mathbf{A} & 0\end{array}\right]</math>

This is because the [[Karush–Kuhn–Tucker]] conditions of the QP problem can be written as:

In fact, most QP solvers work on the LCP formulation, including the [[interior point method]], principal / complementarity pivoting and [[active set]] methods.

:<math>\begin{cases}

v = Q x - A^T {\lambda} + c \\

s = A x - b \\

x, {\lambda}, v, s \geqslant 0 \\

x^{T} v+ {\lambda}^T s = 0

\end{cases}</math>

with ''v'' the Lagrange multipliers on the non-negativity constraints, ''λ'' the <!-- Lagrange -->multipliers on the inequality constraints, and ''s'' the slack variables for the inequality constraints. The fourth condition derives from the complementarity of each group of variables {{math|(''x'', ''s'')}} with its set of KKT vectors (optimal Lagrange multipliers) being {{math|(''v'', ''λ'')}}. In that case,

: <math>z = \begin{bmatrix} x \\ \lambda \end{bmatrix}, \qquad w = \begin{bmatrix} v \\ s \end{bmatrix}</math>

If the non-negativity constraint on the ''x'' is relaxed, the dimensionality of the LCP problem can be reduced to the number of the inequalities, as long as ''Q'' is non-singular (which is guaranteed if it is [[Positive-definite matrix|positive definite]]). The multipliers ''v'' are no longer present, and the first KKT conditions can be rewritten as:

: <math>Q x = A^{T} {\lambda} - c</math>

or:

: <math> x = Q^{-1}(A^{T} {\lambda} - c)</math>

pre-multiplying the two sides by ''A'' and subtracting ''b'' we obtain:

: <math> A x - b = A Q^{-1}(A^{T} {\lambda} - c) -b \,</math>

The left side, due to the second KKT condition, is ''s''. Substituting and reordering:

: <math> s = (A Q^{-1} A^{T}) {\lambda} + (- A Q^{-1} c - b )\,</math>

Calling now

:<math>\begin{align}

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

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

\end{align}</math>

we have an LCP, due to the relation of complementarity between the slack variables ''s'' and their Lagrange multipliers ''λ''. Once we solve it, we may obtain the value of ''x'' from ''λ'' through the first KKT condition.

Finally, it is also possible to handle additional equality constraints:

: <math>A_{eq}x = b_{eq}</math>

This introduces a vector of Lagrange multipliers ''μ'', with the same dimension as <math>b_{eq}</math>.

It is easy to verify that the ''M'' and ''Q'' for the LCP system <math> s = M {\lambda} + Q</math> are now expressed as:

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

q &:= - \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>

From ''λ'' we can now recover the values of both ''x'' and the Lagrange multiplier of equalities ''μ'':

:<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.{{sfnp|Murty|1988}}{{sfnp|Cottle|Pang|Stone|1992}} LCP problems can be solved also by the [[criss-cross algorithm]],{{sfnp|Fukuda|Namiki|1994}}{{sfnp|Fukuda|Terlaky|1997}}{{sfnp|den Hertog|Roos|Terlaky|1993}}{{sfnp|Csizmadia|Illés|2006}} conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.{{sfnp|den 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.{{sfnp|den Hertog|Roos|Terlaky|1993}}{{sfnp|Csizmadia|Illés|2006}}{{sfnp|Cottle|Pang|Venkateswaran|1989}}

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

== See also ==

*[[Complementarity theory]]

*[[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 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 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/ }} (Available for download at the website of Professor [http://www-personal.umich.edu/~murty/ Katta G. Murty].) {{MR|949214}}

* {{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-9}}1 {{MR|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}}

* {{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 |citeseerx=10.1.1.36.9373 |s2cid=2794181 |id=[http://www.cas.mcmaster.ca/~terlaky/files/crisscross.ps Postscript preprint]}}

* {{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|doi-access=free}}

* {{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/ }} (Available for download at the website of Professor |mr=949214|id=[http://www-personal.umich.edu/~murty/ Updated and free PDF version at Katta G. Murty's website]|archive-url=https://web.) {{MRarchive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|949214archive-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 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}}

*{{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 |doi-access=free}}

==Further reading==

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

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

* R. W. Cottle and [[G. B. Dantzig]]. Complementary pivot theory of mathematical programming. ''Linear Algebra and its Applications'', 1:103-125, 1968.

== External links ==

* {{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/ }} (Available for download at the website of Professor [http://www-personal.umich.edu/~murty/ Katta G. Murty].) {{MR|949214}}

* [https://web.archive.org/web/20041029022008/http://www.american.edu/econ/gaussres/optimize/quadprog.src LCPSolve] &mdash; A simple procedure in GAUSS to solve a linear complementarity problem

* [[Siconos]]/Numerics open-source GPL implementation in C of Lemke's algorithm and other methods to solve LCPs and MLCPs

{{Mathematical programming}}

Line 56 ⟶ 129:

[[Category:Linear algebra]]

[[Category:Mathematical optimization]]

[[de:Lineares Komplementaritätsproblem]]