Given a known linear function f(x), where x is a vector, find x such that

• x >= 0
• f(x) >= 0
• x^T f(x) = 0

Since f(x) is a known linear function of the vector x this is equivalent to taking a known matrix M and vector q saying that given M, find x such that

• x >= 0
• f(x) = M x + q >= 0
• x^T f(x) = 0

x^T indicates the transpose of x.

The third line is the "complementarity" condition which means that for EACH element of the vectors x and f(x), either one or both of the two elements must be zero. They thus are complementary to each other.

---

• hopefully helpful alternate wording:

The third line is the "complementarity" condition. It is satisfied only if -- when considering the list of elements making up the vectors x and f(x) -- each element is zero in at least one of the vectors.

---

This type of problem arises with resting contact forces; the resting contact force is complementary to the relative acceleration of the bodies along the contact normal vector. Solving LCP's is non-trivial. This can be seen as a special type of inequality-constrained optimization, where we find x such that f(x) is optimized subject to the inequality constraint f >= 0, with the additional restrictions that x >=0 and x^T f = 0.

--MrLin