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.

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 \mathbf {w} _{i}\mathbf {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 \mathbf {b} }$  as well as ${\displaystyle \mathbf {x} \geq \mathbf {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]}$ 

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

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

• ${\displaystyle \mathbf {s} =\mathbf {A} \mathbf {x} -\mathbf {b} }$ 

• ${\displaystyle \mathbf {x} ,\mathbf {\lambda } ,\mathbf {v} ,\mathbf {s} \geq \mathbf {0} }$ 

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

...being ${\displaystyle \mathbf {v} }$  the multipliers on the non-negativity constraints,${\displaystyle \mathbf {\lambda } }$  the multipliers on the inequality constraints, and ${\displaystyle \mathbf {s} }$  the slack variables for the inequality constraints. The fourth condition derives from the complementarity of each group of variables (${\displaystyle \mathbf {x} ,\mathbf {s} }$ ) with its set of KKT multipliers (${\displaystyle \mathbf {v} ,\mathbf {\lambda } }$ ).

In that case,

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

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

If the non-negativity constraint on the ${\displaystyle \mathbf {x} }$  is relaxed, the dimensionality of the LCP problem can be reduced to the number of the inequalities, as long as ${\displaystyle \mathbf {Q} }$  is non-singular (which is guaranteed if it is positive definite). The multipliers ${\displaystyle \mathbf {v} }$  are no longer present, and the first KKT conditions can be rewritten as:

• ${\displaystyle \mathbf {Q} \mathbf {x} =\mathbf {A} ^{T}\mathbf {\lambda } -\mathbf {c} }$ 

or:

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

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

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

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

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

Calling now ${\displaystyle \mathbf {M} =(\mathbf {A} \mathbf {Q} ^{-1}\mathbf {A} ^{T})}$  and ${\displaystyle \mathbf {q} =(-\mathbf {A} \mathbf {Q} ^{-1}\mathbf {c} -\mathbf {b} )}$  we have an LCP, due to the relation of complementarity between the slack variables ${\displaystyle \mathbf {s} }$  and their multipliers ${\displaystyle \mathbf {\lambda } }$ . Once we solve it, we may obtain the value of ${\displaystyle \mathbf {x} }$  from ${\displaystyle \mathbf {\lambda } }$  through the first KKT condition.

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

${\displaystyle \mathbf {A} _{eq}\mathbf {x} =\mathbf {b} _{eq}}$ 

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

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

${\displaystyle \mathbf {M} =(\left[{\begin{array}{cc}\mathbf {A} &\mathbf {0} \end{array}}\right]\left[{\begin{array}{cc}\mathbf {Q} &\mathbf {A} _{eq}^{T}\\-\mathbf {A} _{eq}&\mathbf {0} \end{array}}\right]^{-1}\left[{\begin{array}{cc}\mathbf {A} ^{T}\\\mathbf {0} \end{array}}\right])}$ 

${\displaystyle \mathbf {q} =(-\left[{\begin{array}{cc}\mathbf {A} &\mathbf {0} \end{array}}\right]\left[{\begin{array}{cc}\mathbf {Q} &\mathbf {A} _{eq}^{T}\\-\mathbf {A} _{eq}&\mathbf {0} \end{array}}\right]^{-1}\left[{\begin{array}{c}\mathbf {c} \\\mathbf {b} _{eq}\end{array}}\right]-\mathbf {b} )}$ 

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

${\displaystyle \left[{\begin{array}{c}\mathbf {x} \\\mathbf {\mu } \end{array}}\right]=\left[{\begin{array}{cc}\mathbf {Q} &\mathbf {A} _{eq}^{T}\\-\mathbf {A} _{eq}&\mathbf {0} \end{array}}\right]^{-1}\left[{\begin{array}{c}\mathbf {A} ^{T}\mathbf {\lambda } -\mathbf {c} \\-\mathbf {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.

See also

• Criss-cross algorithm
• 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.
• Fukuda, Komei; Namiki, Makoto (1994). "On extremal behaviors of Murty's least index method". Mathematical Programming. 64 (1): 365–370. doi:10.1007/BF01582581. MR 1286455. {{cite journal}}: Cite has empty unknown parameter: |1= (help); Invalid |ref=harv (help); Unknown parameter |month= ignored (help)
• Fukuda, Komei; Terlaky, Tamás (1997). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming: Series B. 79 (Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997). Amsterdam: North-Holland Publishing Co.: 369–395. doi:10.1016/S0025-5610(97)00062-2. MR 1464775. Postscript preprint. {{cite journal}}: Cite has empty unknown parameters: |1=, |2=, and |3= (help); Invalid |ref=harv (help); More than one of |number= and |issue= specified (help); Unknown parameter |editors= ignored (|editor= suggested) (help)
• Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. 46–47 (Degeneracy in optimization problems). Springer Netherlands: 203–233. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. PDF file of (1991) preprint. {{cite journal}}: Cite has empty unknown parameter: |1= (help); Invalid |ref=harv (help); More than one of |number= and |issue= specified (help)

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