Linear complementarity problem

In mathematical 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 Dantzig in 1968.

Formulation

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

• ${w} = {Mz} + {q} \,$
• ${w} \ge 0, {z} \ge 0\,$ (that is, each component of these two vectors is non-negative)
• ${w}_i {z}_i = 0\,$ for all i. (The complementarity condition)

A sufficient condition for existence and uniqueness of a solution to this problem is that M be symmetric positive-definite.

The vector ${w}\,$ is a slack variable, and so is generally discarded after ${z}\,$ is found. As such, the problem can also be formulated as:

• ${Mz}+{q} \ge {0}\,$
• ${z} \ge {0}\,$
• ${z}^{\mathrm{T}}({Mz}+{q}) = 0\,$ (the complementarity condition)

Convex quadratic-minimization: Minimum conditions

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

$f({z}) = {z}^{\mathrm{T}}({Mz}+{q})\,$

subject to the constraints

${Mz}+{q} \ge {0}\,$

${z} \ge {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}^T{x}+\frac{1}{2}{x}^T{Qx}\,$ subject to ${Ax} \geq {b} \,$ as well as ${x} \ge {0}\,$ with Q symmetric

is the same as solving the LCP with

• ${q} = \left[\begin{array}{c}{c}\\-{b}\end{array}\right]\,$
• ${M} = \left[\begin{array}{cc} {Q} & -{A}^{T}\\ {A} & 0\end{array}\right]\,$

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

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

• ${s} = {A} {x} - {b}\,$

• ${x}, {\lambda}, {v}, {s} \ge {0}\,$

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

...being ${v} \,$ the Lagrange multipliers on the non-negativity constraints,${\lambda} \,$ 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 (${x}, {s}\,$) with its set of KKT vectors (optimal Lagrange multipliers) being (${v}, {\lambda}\,$).

In that case,

${z} = \left[\begin{array}{c}{x}\\ {\lambda}\end{array}\right]\,$

${w} = \left[\begin{array}{c}{v}\\ {s}\end{array}\right]\,$

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} {\lambda} - {c}\,$

or:

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

pre-multiplying the two sides by ${A}\,$ and subtracting ${b}\,$ we obtain:

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

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

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

Calling now ${M} \,\overset{\underset{\mathrm{def}}{}}{=}\, ({A} {Q}^{-1} {A}^{T})\,$ and ${q} \,\overset{\underset{\mathrm{def}}{}}{=}\, (- {A} {Q}^{-1} {c} - {b})\,$ we have an LCP, due to the relation of complementarity between the slack variables ${s}\,$ and their Lagrange multipliers ${\lambda}\,$. Once we solve it, we may obtain the value of ${x}\,$ from ${\lambda}\,$ 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 ${\mu}\,$, with the same dimension as ${b}_{eq}\,$.

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

${M} ~\overset{\underset{\mathrm{def}}{}}{=}~ (\left[\begin{array}{cc}{A} & {0}\end{array}\right] \left[\begin{array}{cc} {Q} & {A}_{eq}^{T}\\ -{A}_{eq} & {0}\end{array}\right]^{-1} \left[\begin{array}{cc}{A}^{T} \\ {0}\end{array}\right])\,$

${q} ~\overset{\underset{\mathrm{def}}{}}{=}~ (- \left[\begin{array}{cc}{A} & {0}\end{array}\right] \left[\begin{array}{cc} {Q} & {A}_{eq}^{T}\\ -{A}_{eq} & {0}\end{array}\right]^{-1} \left[\begin{array}{c}{c}\\ {b}_{eq}\end{array}\right] - {b})\,$

From ${\lambda}\,$ we can now recover the values of both ${x}\,$ and the Lagrange multiplier of equalities ${\mu}\,$:

$\left[\begin{array}{c}{x}\\ {\mu}\end{array}\right] = \left[\begin{array}{cc} {Q} & {A}_{eq}^{T}\\ -{A}_{eq} & {0}\end{array}\right]^{-1} \left[\begin{array}{c} {A}^{T}{\lambda}-{c}\\-{b}_{eq}\end{array}\right] \,$

In fact, most QP solvers work on the LCP formulation, including the interior point method, principal / complementarity pivoting, and active set methods. LCP problems can be solved also by the criss-cross algorithm, conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix. A sufficient matrix is a generalization both of a positive-definite matrix and of a P-matrix, whose principal minors are each positive. Such LCPs can be solved when they are formulated abstractly using oriented-matroid theory.

See also

• Complementarity theory
• Physics engine Impulse/constraint type physics engines for games use this approach.
• Contact dynamics Contact dynamics with the nonsmooth approach

References

• Cottle, Richard W.; Pang, Jong-Shi; Stone, Richard E. (1992). The linear complementarity problem. Computer Science and Scientific Computing. Boston, MA: Academic Press, Inc.. pp. xxiv+762 pp.. ISBN 0-12-192350-9. MR1150683. 
• Cottle, R. W.; Pang, J.-S.; Venkateswaran, V. (March–April 1989). "Sufficient matrices and the linear complementarity problem". Linear Algebra and its Applications 114–115: 231–249. doi:10.1016/0024-3795(89)90463-1. MR986877. http://www.sciencedirect.com/science/article/pii/0024379589904631. 
• Csizmadia, Zsolt; Illés, Tibor (2006). "New criss-cross type algorithms for linear complementarity problems with sufficient matrices" (pdf). Optimization Methods and Software 21 (2): 247–266. doi:10.1080/10556780500095009. MR2195759. http://www.cs.elte.hu/opres/orr/download/ORR03_1.pdf. 
• Fukuda, Komei; Namiki, Makoto (March 1994). "On extremal behaviors of Murty's least index method". Mathematical Programming 64 (1): 365–370. doi:10.1007/BF01582581. MR1286455. 
• den Hertog, D.; Roos, C.; Terlaky, T. (1 July 1993). "The linear complementarity problem, sufficient matrices, and the criss-cross method" (pdf). Linear Algebra and its Applications 187: 1–14. doi:10.1016/0024-3795(93)90124-7. http://arno.uvt.nl/show.cgi?fid=72943. 
• Murty, K. G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp.. ISBN 3-88538-403-5. MR949214. Updated and free PDF version at Katta G. Murty's website. http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/. 
• Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling and Dominique de Werra. ed. "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming: Series B (Amsterdam: North-Holland Publishing Co.) 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997): 369–395. doi:10.1016/S0025-5610(97)00062-2. MR1464775. Postscript preprint. 
• Todd, Michael J. (1985). "Linear and quadratic programming in oriented matroids". Journal of Combinatorial Theory. Series B 39 (2): 105–133. doi:10.1016/0095-8956(85)90042-5. MR811116. 

Further reading

• R. W. Cottle and G. B. Dantzig. Complementary pivot theory of mathematical programming. Linear Algebra and its Applications, 1:103-125, 1968.
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research (Springer Netherlands) 46–47 (1): 203–233. doi:10.1007/BF02096264. ISSN 0254-5330. MR1260019. PDF file of (1991) preprint. 

External links

• LCPSolve — A simple procedure in GAUSS to solve a linear complementarity problem
• LCPSolve.py — A Python/NumPy implementation of LCPSolve is part of OpenOpt since its release 0.32
• Siconos/Numerics open-source GPL implementation in C of Lemke's algorithm and other methods to solve LCPs amd MLCPs