Linear complementarity problem

From Wikipedia, the free encyclopedia

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:

$\mathbf{Mx}+\mathbf{b} > \mathbf{0}$ and $\mathbf{x} > \mathbf{0}$ ; that is, each component of these two vectors is positive, and
$\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.

[edit] Relation to Quadratic Programming

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

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

subject to the constraints

$\mathbf{Mx}+\mathbf{b} > \mathbf{0}$ and $\mathbf{x} > \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, for the case that M is symmetric positive-semidefinite.

[edit] 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.