Linear complementarity problem

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:

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

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} ge mathbf{0} and mathbf{x} ge 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.

If M is positive definite, any algorithm for solving (convex) QPs can of course be used to solve an LCP. However, there also exist more efficient, specialized algorithms, such as Lemke's algorithm and Dantzig's algorithm.

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


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Linear Complementarity Problem — Das lineare Komplementaritätsproblem (LKP, engl. linear complementarity problem) ist ein mathematisches Problem aus der Linearen Algebra. Gegeben sei eine rationale Matrix und ein rationaler Vektor , dann finde Vektoren so, dass die drei… …   Deutsch Wikipedia

  • Mixed linear complementarity problem — In mathematical optimization theory, the mixed linear complementarity problem, often abbreviated as MLCP or LMCP, is a generalization of the linear complementarity problem to include free variables. References Complementarity problems Algorithms… …   Wikipedia

  • Mixed complementarity problem — (MCP) is a problem formulation in mathematical programming. Many well known problem types are special cases of, or may be reduced to MCP. It is a generalization of Nonlinear complementarity problem (NCP). Definition The mixed complementarity… …   Wikipedia

  • Nonlinear complementarity problem — In applied mathematics, a nonlinear complementarity problem (NCP) with respect to a mapping ƒ : Rn → Rn, denoted by NCPƒ, is to find a vector x ∈ Rn such that where ƒ(x) is a smooth mapping. References Stephen C.… …   Wikipedia

  • Linear programming — (LP, or linear optimization) is a mathematical method for determining a way to achieve the best outcome (such as maximum profit or lowest cost) in a given mathematical model for some list of requirements represented as linear relationships.… …   Wikipedia

  • Complementarity theory — This article is related to mathematical programming. For other uses see complementarity. A complementarity problem is a type of mathematical optimization problem. It is the problem of optimizing (minimizing or maximizing) a function of two vector …   Wikipedia

  • Quantum mind–body problem — The quantum mind–body problem refers to the philosophical discussions of the mind–body problem in the context of quantum mechanics. Since quantum mechanics involves quantum superpositions, which are not perceived by observers, some… …   Wikipedia

  • Criss-cross algorithm — This article is about an algorithm for mathematical optimization. For the naming of chemicals, see crisscross method. The criss cross algorithm visits all 8 corners of the Klee–Minty cube in the worst case. It visits 3 additional… …   Wikipedia

  • List of numerical analysis topics — This is a list of numerical analysis topics, by Wikipedia page. Contents 1 General 2 Error 3 Elementary and special functions 4 Numerical linear algebra …   Wikipedia

  • Complémentarité linéaire — En mathématiques, et plus spécialement en recherche opérationnelle et en optimisation, un problème de complémentarité linéaire est défini par la donnée d une matrice et d un vecteur et consiste à trouver un vecteur tel que ses composantes et… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”