Linear complementarity problem: Difference between revisions

Revision as of 03:33, 5 July 2009

Revision as of 17:13, 16 July 2009

Line 1:

In mathematical [[optimization (mathematics)|optimization theory]], the '''linear complementarity problem''', or '''LCP''', is a special case of [[quadratic programming]] which arises frequently in [[computational mechanics]]. Given a real matrix '''M''' and vector '''b''', the linear complementarity problem seeks a vector '''x''' which satisfies the following two constraints:

== Formulation ==

* <math>\mathbf{Mx}+\mathbf{b} \ge \mathbf{0}</math> and <math>\mathbf{x} \ge \mathbf{0}</math>; that is, each component of these two vectors is non-negative, and

Given a real matrix '''M''' and vector '''q''', the linear complementarity problem seeks a vector '''z''' and '''w''' which satisfies the following constraints:

* <math>\mathbf{x}^{\mathrm{T}}(\mathbf{Mx}+\mathbf{b}) = 0</math>, the '''complementarity condition'''.

* <math>\mathbf{w} - \mathbf{Mz} = \mathbf{q} </math>

* <math>\mathbf{Mx}+\mathbf{bw} \ge \mathbf{0}</math>, and <math>\mathbf{xz} \ge \mathbf{0}</math>; (that is, each component of these two vectors is non-negative, and)

* <math>\mathbf{w}_i \mathbf{z}_i = 0</math> for all i. (The [[Complementarity theory |complementarity]] condition)

A sufficient condition for existence and uniqueness of a solution to this problem is that '''M''' be [[Symmetric matrix|symmetric]] [[Positive-definite matrix|positive-definite]].

The vector <math>\mathbf{w}</math> is a [[slack variable]], and so is generally discarded after <math>\mathbf{z}</math> is found. As such, the problem can also be formulated as:

* <math>\mathbf{Mz}+\mathbf{q} \ge \mathbf{0}</math>

* <math>\mathbf{x} \ge \mathbf{0}</math>

* <math>\mathbf{xz}^{\mathrm{T}}(\mathbf{MxMz}+\mathbf{bq}) = 0</math>, (the '''complementarity condition'''.)

==Relation to Quadratic Programming==

Line 10 ⟶ 20:

Finding a solution to the linear complementarity problem is equivalent to minimizing the quadratic function

<math>f(\mathbf{xz}) = \mathbf{xz}^{\mathrm{T}}(\mathbf{MxMz}+\mathbf{bq})</math>

subject to the constraints

* <math>\mathbf{MxMz}+\mathbf{bq} \ge \mathbf{0}</math> and
* <math>\mathbf{xz} \ge \mathbf{0}</math>.

Indeed,Because these constraints ensure that ''f'' is always non-negative, so that it attains aits minimum of 0 at '''xz''' if and only if '''xz''' solves the linear complementarity problem.

If '''M''' is [[Positive-definite matrix|positive definite]], any algorithm for solving (convex) [[Quadratic programming|QPs]] can of course be used to solve anthe LCP. However, there also exist more efficient, specialized algorithms, such as [[Lemke's algorithm]] and [[Dantzig's algorithm]].

== See also ==

*[[Complementarity theory]]

*[[Physics engine]] Impulse/constraint type physics engines for games use this approach.

== References ==

* [http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/ Linear Complementarity webbook]

* [http://www.uclm.es/area/gsee/Web/Raquel/Complementarity_Problems.pdf Complementarity problems]

==Further reading==