Linear Complementarity Problem

A math problem asking for two sets of non-negative variables where one being positive forces the other to be zero — what contact-force solving reduces to.

The linear complementarity problem was formulated by Cottle and Dantzig in 1968: given a matrix M and a vector q, find non-negative vectors z and w such that w = Mz + q, with the added condition that for each corresponding pair of components, at least one of z or w must be zero (the complementarity condition). In simulation, this describes contact exactly: two objects either have a gap between them, with zero contact force, or are pressed together, with positive contact force, and the two situations can never hold at once — a physics engine has to solve for contact forces satisfying this kind of condition at every step. ODE's contact and friction model is based on Dantzig's LCP solver, and game engines commonly use iterative methods like Projected Gauss-Seidel to approximate a solution. MuJoCo, by contrast, notes that LCPs with friction are NP-hard, and instead uses a convex soft-contact model that relaxes the complementarity condition.

ExampleA box resting still on a table has zero normal gap and a positive supporting force; once the box is lifted off the table, the gap becomes positive and the supporting force drops to zero. Solving for exactly this pair of complementary conditions is what the solver does at every step.

Also called

LCP

Related

Contact Model · Constraint Solver · Projected Gauss-Seidel · Coulomb Friction · Soft Contact Model · Physics Engine

Sources

Linear complementarity problem - Wikipedia
MuJoCo Documentation: Computation
ODE Manual