Linear complementarity problem: Difference between revisions

Revision as of 17:43, 20 March 2008

Revision as of 23:03, 9 June 2008

Line 1:

In mathematical [[optimization (mathematics)|optimization theory]], the '''linear complementarity problem''', inor '''LCP''', is a special case of [[linearquadratic algebraprogramming]] consistswhich ofarises startingfrequently with a known ''n''-dimensionalin [[columncomputational vectormechanics]]. '''''q''''' andGiven a knownreal matrix ''n'M'×''n'' [[matrixand (mathematics)|matrix]]vector '''''M''b''', andthe findinglinear twocomplementarity ''n''-dimensionalproblem vectorsseeks '''''w'''''a andvector '''''z''x''' suchwhich satisfies the following two thatconstraints:

#'''''q''''' = '''''w''''' − '''''Mz'''''

#''w_i'' ≥ 0 and ''z_i'' ≥ 0 for each ''i''

#''w_i''×''z_i'' = 0 (i.e. either ''w_i'' = 0 or ''z_i'' = 0) for each ''i''

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

There are several [[algorithm]]s (e.g. [[Lemke's algorithm]]) dealing with specific cases of the linear complementarity problem.

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

A linear complementarity problem has a unique solution if and only if '''''M''''' is a [[P-matrix]].

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

==See also==

*[[Quadratic programming]]

==Relation to Quadratic Programming==

*[[Optimization (mathematics)]]

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

<math>f(\mathbf{x}) = \mathbf{x}^{\mathrm{T}}(\mathbf{Mx}+\mathbf{b})</math>

subject to the constraints

<math>\mathbf{Mx}+\mathbf{b} > \mathbf{0}</math> and <math>\mathbf{x} > \mathbf{0}</math>.

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.

==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.

[[Category:Linear algebra]][[Category:Optimization]]