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.Template:SfnpTemplate:SfnpTemplate:Sfnp

Formulation

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⩾0,$ (that is, each component of these two vectors is non-negative)
• $z^{T}w=0$ or equivalently $\sum _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 Template:Math has a solution for every q, then M is a Q-matrix. If M is such that Template:Math have a unique solution for every q, then M is a P-matrix. Both of these characterizations are sufficient and necessary.Template:Sfnp

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

• $Mz+q⩾0$
• $z⩾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^T(Mz+q)$

subject to the constraints

$Mz+q⩾0$

$z⩾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⩾b$ as well as $x⩾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:

$\{\begin{array}{c}v=Qx-A^T\lambda +c\\ s=Ax-b\\ x,\lambda ,v,s⩾0\\ x^{T}v+{\lambda }^{T}s=0\end{array}$

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 Template:Math with its set of KKT vectors (optimal Lagrange multipliers) being Template:Math. 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:

$Qx=A^T\lambda -c$

or:

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

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

$Ax-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

$\begin{array}{cc}M& :=(A{Q}^{-1}{A}^T)\\ q& :=(-A{Q}^{-1}c-b)\end{array}$

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\lambda +Q$ are now expressed as:

$\begin{array}{cc}M& :=\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}{A}^T\\ 0\end{array}\right]\\ q& :=-\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\end{array}$

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

$\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.Template:SfnpTemplate:Sfnp LCP problems can be solved also by the criss-cross algorithm,Template:SfnpTemplate:SfnpTemplate:SfnpTemplate:Sfnp conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.Template:SfnpTemplate:Sfnp A sufficient matrix is a generalization both of a positive-definite matrix and of a P-matrix, whose principal minors are each positive.Template:SfnpTemplate:SfnpTemplate:Sfnp Such LCPs can be solved when they are formulated abstractly using oriented-matroid theory.Template:SfnpTemplate:SfnpTemplate:Sfnp

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 games can be reduced to LCP.

References

• Template:Cite book
• Template:Cite journal
• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite journal
• Template:Cite journal

Further reading

• Template:Cite web

External links

• 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