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.^[1][2][3]

Formulation

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

• ${\displaystyle {w}\geq 0,{z}\geq 0\,}$  (that is, each component of these two vectors is non-negative)
• ${\displaystyle z^{T}w=0}$  or equivalently ${\displaystyle \Sigma _{i}{w}_{i}{z}_{i}=0\,}$ . This is the complementarity condition, since it implies that at most one of each pair ${\displaystyle \{w_{i},z_{i}\}}$  can be positive.
• ${\displaystyle {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 LCP(M,q) have a solution for every q, then M is a Q-matrix. If M is such that LCP(M,q) have a unique solution for every q, then M is a P-matrix. Both of these characterizations are sufficient and necessary.^[4]

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

• ${\displaystyle {Mz}+{q}\geq {0}\,}$ 
• ${\displaystyle {z}\geq {0}\,}$ 
• ${\displaystyle {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

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

subject to the constraints

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

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

is the same as solving the LCP with

• ${\displaystyle {q}=\left[{\begin{array}{c}{c}\\-{b}\end{array}}\right]\,}$ 
• ${\displaystyle {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:

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

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

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

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

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

In that case,

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

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

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

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

or:

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

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

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

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

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

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

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

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

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

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

${\displaystyle {M}~{\overset {\underset {\mathrm {def} }{}}{=}}~\left(\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]\right)\,}$ 

${\displaystyle {q}~{\overset {\underset {\mathrm {def} }{}}{=}}~\left(-\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}\right)\,}$ 

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

${\displaystyle \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.^[1][2] LCP problems can be solved also by the criss-cross algorithm,^[6][7][8][9] conversely, for linear complementarity problems, the criss-cross algorithm terminates finitely only if the matrix is a sufficient matrix.^[8][9] A sufficient matrix is a generalization both of a positive-definite matrix and of a P-matrix, whose principal minors are each positive.^[8][9][10] Such LCPs can be solved when they are formulated abstractly using oriented-matroid theory.^[11][12][13]

See also

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

Notes

1. Murty (1988)
2. Cottle, Pang & Stone (1992)
3. R. W. Cottle and G. B. Dantzig. Complementary pivot theory of mathematical programming. Linear Algebra and its Applications, 1:103-125, 1968.
4. Murty, Katta G. (January 1972). "On the number of solutions to the complementarity problem and spanning properties of complementary cones". Linear Algebra and its Applications. 5 (1): 65–108. doi:10.1016/0024-3795(72)90019-5.
5. Taylor, Joshua Adam (2015), Convex Optimization of Power Systems, Cambridge University Press, p. 172, ISBN 9781107076877.
6. Fukuda & Namiki (1994)
7. Fukuda & Terlaky (1997)
8. 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.
9. 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. {{cite journal}}: Cite has empty unknown parameter: |1= (help)
10. 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. MR 0986877. {{cite journal}}: Invalid |ref=harv (help)
11. Todd (1985)
12. Terlaky & Zhang (1993) harvtxt error: multiple targets (2×): CITEREFTerlakyZhang1993 (help): Terlaky, Tamás; Zhang, Shu Zhong (1993). "Pivot rules for linear programming: A Survey on recent theoretical developments". Annals of Operations Research. Degeneracy in optimization problems. 46–47 (1). Springer Netherlands: 203–233. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. CiteSeer^x: 10.1.1.36.7658 . {{cite journal}}: Cite has empty unknown parameter: |1= (help); Invalid |ref=harv (help)
13. Björner, Anders; Las Vergnas, Michel; Sturmfels, Bernd; White, Neil; Ziegler, Günter (1999). "10 Linear programming". Oriented Matroids. Cambridge University Press. pp. 417–479. doi:10.1017/CBO9780511586507. ISBN 978-0-521-77750-6. MR 1744046.

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. MR 1150683. {{cite book}}: Invalid |ref=harv (help)
• 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. MR 0986877. {{cite journal}}: Invalid |ref=harv (help)
• 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. {{cite journal}}: Cite has empty unknown parameter: |1= (help)
• 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. MR 1286455. {{cite journal}}: Invalid |ref=harv (help)
• 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. {{cite journal}}: Invalid |ref=harv (help)
• 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. MR 0949214. Updated and free PDF version at Katta G. Murty's website. {{cite book}}: Invalid |ref=harv (help)
• Fukuda, Komei; Terlaky, Tamás (1997). "Criss-cross methods: A fresh view on pivot algorithms". Mathematical Programming: Series B. Papers from the 16th International Symposium on Mathematical Programming held in Lausanne, 1997. 79 (1–3). Amsterdam: North-Holland Publishing Co.: 369–395. doi:10.1007/BF02614325. MR 1464775. Postscript preprint. {{cite journal}}: Cite has empty unknown parameters: |1= and |2= (help); Invalid |ref=harv (help); Unknown parameter |editors= ignored (|editor= suggested) (help)
• 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. MR 0811116. {{cite journal}}: Invalid |ref=harv (help)
• R. Chandrasekaran. "Bimatrix games" (PDF). pp. 5–7. Retrieved 18 December 2015.

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. Degeneracy in optimization problems. 46–47 (1). Springer Netherlands: 203–233. doi:10.1007/BF02096264. ISSN 0254-5330. MR 1260019. CiteSeer^x: 10.1.1.36.7658 . {{cite journal}}: Cite has empty unknown parameter: |1= (help); Invalid |ref=harv (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
• Siconos/Numerics open-source GPL implementation in C of Lemke's algorithm and other methods to solve LCPs and MLCPs