linear complementarity problem

Given a real matrix M and vector q, the linear complementarity problem LCP(q, M) seeks vectors z and w which satisfy the following constraints:

• $w,\; z\; \backslash geqslant\; 0,$ (that is, each component of these two vectors is non-negative)
• $z^Tw\; =\; 0$ or equivalently $\backslash sum\backslash nolimits\_i\; w\_i\; z\_i\; =\; 0.$ This is the complementarity condition, since it implies that, for all $i$, at most one of $w\_i$ and $z\_i$ can be positive.
• $w\; =\; Mz\; +\; q$

A sufficient condition for existence and uniqueness of a solution to this problem is that M be symmetric 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 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:

• $Mz+q\; \backslash geqslant\; 0$
• $z\; \backslash geqslant\; 0$
• $z^\{\backslash mathrm\{T\}\}(Mz+q)\; =\; 0$ (the complementarity condition)

Finding a solution to the linear complementarity problem is associated with minimizing the quadratic function

: $f(z)\; =\; z^T(Mz+q)$

subject to the constraints

: $\{Mz\}+q\; \backslash geqslant\; 0$

: $z\; \backslash geqslant\; 0$

These constraints ensure that f is always non-negative. The minimum of f is 0 at z if and only if z solves the linear complementarity problem.

If M is positive definite, any algorithm for solving (strictly) convex QPs can solve the LCP. Specially designed basis-exchange pivoting algorithms, such as Lemke's algorithm and a variant of the simplex 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 $f(x)=c^Tx+\backslash tfrac\{1\}\{2\}\; x^T\; Qx$ subject to $Ax\; \backslash geqslant\; b$ as well as $x\; \backslash geqslant\; 0$ with Q symmetric

is the same as solving the LCP with

:

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

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

with v the Lagrange multipliers on the non-negativity constraints, λ the 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,

: $z\; =\; \backslash begin\{bmatrix\}\; x\; \backslash \backslash \; \backslash lambda\; \backslash end\{bmatrix\},\; \backslash qquad\; w\; =\; \backslash begin\{bmatrix\}\; v\; \backslash \backslash \; s\; \backslash end\{bmatrix\}$

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). The multipliers v are no longer present, and the first KKT conditions can be rewritten as:

: $Q\; x\; =\; A^\{T\}\; \{\backslash lambda\}\; -\; c$

or:

: $x\; =\; Q^\{-1\}(A^\{T\}\; \{\backslash lambda\}\; -\; c)$

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

: $A\; x\; -\; b\; =\; A\; Q^\{-1\}(A^\{T\}\; \{\backslash lambda\}\; -\; c)\; -b\; \backslash ,$

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

: $s\; =\; (A\; Q^\{-1\}\; A^\{T\})\; \{\backslash lambda\}\; +\; (-\; A\; Q^\{-1\}\; c\; -\; b\; )\backslash ,$

Calling now

:$\backslash begin\{align\}$

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

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

\end{align}

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:

: $A\_\{eq\}x\; =\; b\_\{eq\}$

This introduces a vector of Lagrange multipliers μ, with the same dimension as $b\_\{eq\}$.

It is easy to verify that the M and Q for the LCP system $s\; =\; M\; \{\backslash lambda\}\; +\; Q$ are now expressed as:

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

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

:

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 matrix is a generalization both of a positive-definite matrix and of a P-matrix, whose principal minors 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 theory.{{sfnp|Todd|1985|}}{{sfnp|Terlaky|Zhang|1993}}{{sfnp|Björner|Las Vergnas|Sturmfels|White|1999}}

• Complementarity theory
• Physics engine Impulse/constraint type physics engines for games use this approach.
• Contact dynamics Contact dynamics with the nonsmooth approach.
• Bimatrix games can be reduced to LCP.

{{Reflist|24em}}

• {{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}}
• {{cite journal|first1=Komei|last1=Fukuda |first2=Tamás|last2=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 |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]|archive-url=https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/|archive-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 |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}}

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

• [https://web.archive.org/web/20041029022008/http://www.american.edu/econ/gaussres/optimize/quadprog.src LCPSolve] — 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}}

Category:Linear algebra

Category:Mathematical optimization