Linear complementarity problem
In mathematical
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:
- (that is, each component of these two vectors is non-negative)
- or equivalently This is the complementarity condition, since it implies that, for all , at most one of and can be positive.
A sufficient condition for existence and uniqueness of a solution to this problem is that M be
The vector w is a slack variable,[5] and so is generally discarded after z is found. As such, the problem can also be formulated as:
- (the complementarity condition)
Convex quadratic-minimization: Minimum conditions
Finding a solution to the linear complementarity problem is associated with minimizing the quadratic function
subject to the constraints
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
Also, a quadratic-programming problem stated as minimize subject to as well as with Q symmetric
is the same as solving the LCP with
This is because the
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 (x, s) with its set of KKT vectors (optimal Lagrange multipliers) being (v, λ). In that case,
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
or:
pre-multiplying the two sides by A and subtracting b we obtain:
The left side, due to the second KKT condition, is s. Substituting and reordering:
Calling now
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:
This introduces a vector of Lagrange multipliers μ, with the same dimension as .
It is easy to verify that the M and Q for the LCP system are now expressed as:
From λ we can now recover the values of both x and the Lagrange multiplier of equalities μ:
In fact, most QP solvers work on the LCP formulation, including the
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.
- Bimatrix games can be reduced to LCP.
Notes
- ^ a b Murty (1988).
- ^ a b Cottle, Pang & Stone (1992).
- ^ Cottle & Dantzig (1968).
- ^ Murty (1972).
- ^ Taylor (2015), p. 172.
- ^ Fukuda & Namiki (1994).
- ^ Fukuda & Terlaky (1997).
- ^ a b c den Hertog, Roos & Terlaky (1993).
- ^ a b c Csizmadia & Illés (2006).
- ^ Cottle, Pang & Venkateswaran (1989).
- ^ Todd (1985).
- ^ Terlaky & Zhang (1993).
- ^ Björner et al. (1999).
References
- MR 1744046.
- Cottle, R. W.; .
- 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. MR 1150683.
- MR 0986877.
- 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. S2CID 24418835.
- S2CID 21476636.
- Fukuda, Komei; Terlaky, Tamás (1997). Thomas M. Liebling; Dominique de Werra (eds.). "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): 369–395. S2CID 2794181. Postscript preprint.
- 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. .
- Murty, Katta G. (January 1972). "On the number of solutions to the complementarity problem and spanning properties of complementary cones" (PDF). Linear Algebra and Its Applications. 5 (1): 65–108. hdl:2027.42/34188.
- Murty, K. G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. Vol. 3. Berlin: Heldermann Verlag. on 2010-04-01.
- Taylor, Joshua Adam (2015). Convex Optimization of Power Systems. Cambridge University Press. ISBN 9781107076877.
- 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): 203–233. S2CID 6058077.
- MR 0811116.
Further reading
- R. Chandrasekaran. "Bimatrix games" (PDF). pp. 5–7. Retrieved 18 December 2015.