Linear complementarity problem

In mathematical 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:

• ${\displaystyle \mathbf {Mx} +\mathbf {b} \geq \mathbf {0} }$ and ${\displaystyle \mathbf {x} \geq \mathbf {0} }$; that is, each component of these two vectors is non-negative, and
• ${\displaystyle \mathbf {x} ^{\mathrm {T} }(\mathbf {Mx} +\mathbf {b} )=0}$, the complementarity condition.

A sufficient condition for existence and uniqueness of a solution to this problem is that M be symmetric positive-definite.

Relation to Quadratic Programming

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

${\displaystyle f(\mathbf {x} )=\mathbf {x} ^{\mathrm {T} }(\mathbf {Mx} +\mathbf {b} )}$ 

subject to the constraints

${\displaystyle \mathbf {Mx} +\mathbf {b} \geq \mathbf {0} }$  and ${\displaystyle \mathbf {x} \geq \mathbf {0} }$ .

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

Although any quadratic programming algorithm can solve an LCP, there exist more efficient, specialized algorithms, such as Lemke's algorithm and Dantzig's algorithm.

See also

• Complementarity theory

Further reading

• Cottle, Richard W. et al. (1992) The linear complementarity problem. Boston, Mass. : Academic Press
• R. W. Cottle and G. B. Dantzig. Complementary pivot theory of mathematical programming. Linear Algebra and its Applications, 1:103-125, 1968.