Linear complementarity problem

In mathematical optimization theory, the linear complementarity problem (LCP) is a special case of quadratic programming which arises frequently in computational mechanics.

Formulation

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

• ${\displaystyle \mathbf {w} =\mathbf {Mz} +\mathbf {q} }$ 
• ${\displaystyle \mathbf {w} \geq 0,\mathbf {z} \geq 0}$  (that is, each component of these two vectors is non-negative)
• ${\displaystyle {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 ${\displaystyle \mathbf {w} }$  is a slack variable, and so is generally discarded after ${\displaystyle \mathbf {z} }$  is found. As such, the problem can also be formulated as:

• ${\displaystyle \mathbf {Mz} +\mathbf {q} \geq \mathbf {0} }$ 
• ${\displaystyle \mathbf {z} \geq \mathbf {0} }$ 
• ${\displaystyle \mathbf {z} ^{\mathrm {T} }(\mathbf {Mz} +\mathbf {q} )=0}$  (the complementarity condition)

Relation to quadratic programming

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

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

subject to the constraints

${\displaystyle \mathbf {Mz} +\mathbf {q} \geq \mathbf {0} }$ 

${\displaystyle \mathbf {z} \geq \mathbf {0} }$ 

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

If M is positive definite, any algorithm for solving (convex) QPs can of course be used to solve the LCP. However, there also exist more efficient, specialized algorithms, such as Lemke's algorithm and Dantzig's algorithm.

Also, a quadratic programming problem stated as minimize ${\displaystyle f(\mathbf {x} )=\mathbf {c} ^{T}\mathbf {x} +{\frac {1}{2}}\mathbf {x} ^{T}\mathbf {Qx} }$  subject to ${\displaystyle \mathbf {Ax} \geq 0}$ 

is the same as solving the LCP with

• ${\displaystyle \mathbf {q} =\left[{\begin{array}{c}\mathbf {c} \\-\mathbf {b} \end{array}}\right]}$ 
• ${\displaystyle \mathbf {M} =\left[{\begin{array}{cc}\mathbf {Q} &-\mathbf {A} ^{T}\\\mathbf {A} &0\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.

See also

• Complementarity theory
• Physics engine Impulse/constraint type physics engines for games use this approach.

References

• Murty, K. G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. Vol. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp. ISBN 3-88538-403-5. (Available for download at the website of Professor Katta G. Murty.) MR 0949214

Further reading

• 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. MR 1150683
• R. W. Cottle and G. B. Dantzig. Complementary pivot theory of mathematical programming. Linear Algebra and its Applications, 1:103-125, 1968.
• Murty, K. G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. Vol. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp. ISBN 3-88538-403-5. (Available for download at the website of Professor Katta G. Murty.) MR 0949214