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

This topic: WorldFoundry > LinearComplementarityProblem
Topic revision: 24 Oct 2004, ExecutionStyle;
This site is powered by FoswikiCopyright © by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding Foswiki? Send feedback