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 variables subject to certain requirements (constraints) which include: that the inner product of the two variables must equal zero, i.e. <X, Y> = 0.^[1] In particular for finite-dimensional real vector spaces this means that, if one has vectors X and Y with nonnegative components (x_i ≥ 0 and y_i ≥ 0 for all i: in the first quadrant if 2-dimensional, in the first octant if 3-dimensional), then for each pair of components x_i and y_i one of the pair must be zero, hence the name complementarity. e.g. X = (1, 0) and Y = (0, 2) are complementary, but X = (1, 1) and Y = (2, 0) are not. A complementarity problem is a special case of a variational inequality.

History

Complementarity problems were originally studied because the Karush–Kuhn–Tucker conditions in linear programming and quadratic programming constitute a linear complementarity problem (LCP) or a mixed complementarity problem (MCP). In 1963 Lemke and Howson showed that, for two person games, computing a Nash equilibrium point is equivalent to an LCP. In 1968 Cottle and Dantzig unified linear and quadratic programming and bimatrix games. Since then the study of complementarity problems and variational inequalities has expanded enormously.

Areas of mathematics and science that contributed to the development of complementarity theory include: optimization, equilibrium problems, variational inequality theory, fixed point theory, topological degree theory and nonlinear analysis.

See also

• Mathematical programming with equilibrium constraints
• nl format for representing complementarity problems

References

1. ^ Billups, Stephen; Murty, Katta (1999). Complementarity Problems  http://www-personal.umich.edu/~murty/LCPart.ps

Further reading

• Richard W. Cottle, Jong-Shi Pang, Richard E. Stone (1992). The Linear Complementarity Problem. Academic Press. ISBN 978-0121923501. 
• George Isac (1992). Complementarity Problems. Springer. ISBN 978-3540562511. 
• George Isac (2000). Topological Methods in Complementarity Theory. Springer. ISBN 978-0792362746. 
• Francisco Facchinei, Jong-Shi Pang (2003). Finite-Dimensional Variational Inequalities and Complementarity Problems: v.1 and v.2. Springer. ISBN 978-0387955803. 
• Murty, K. G. (1988). Linear complementarity, linear and nonlinear programming. Sigma Series in Applied Mathematics. 3. Berlin: Heldermann Verlag. pp. xlviii+629 pp.. ISBN 3-88538-403-5. http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/.  (Available for download at the website of Professor Katta G. Murty.) MR949214

Collections

• Richard Cottle, F. Giannessi, Jacques Louis Lions, ed (1980). Variational Inequalities and Complementarity Problems: Theory and Applications. John Wiley & Sons. ISBN 978-0471276104. 
• Michael C. Ferris, Jong-Shi Pang, ed (1997). Complementarity and Variational Problems: State of the Art. SIAM. ISBN 978-0898713916. 

External links

• CPNET:Complementarity Problem Net

This mathematical analysis–related article is a stub. You can help Wikipedia by expanding it.v · Categories: Mathematical optimization Functional analysis Topology Numerical analysis Mathematical analysis stubs Wikimedia Foundation. 2010. Игры ⚽ Поможем решить контрольную работу Craig Ritter Arlie William Schorger Look at other dictionaries: Complementarity — may refer to: Contents 1 Mathematics 2 Physical sciences 3 Social sciences …   Wikipedia Complementarity (physics) — In physics, complementarity is a basic principle of quantum theory proposed by Niels Bohr, closely identified with the Copenhagen interpretation, and refers to effects such as the wave–particle duality. Just like the finitude of the speed of… …   Wikipedia 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 …   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 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 O-Ring theory of economic development — The O Ring Theory of Economic Development is a model of economic development put forward by Michael Kremer which proposes that tasks of production must be executed proficiently together in order for any of them to be of high value. The key… …   Wikipedia De Broglie–Bohm theory — Quantum mechanics Uncertainty principle …   Wikipedia Old quantum theory — Quantum mechanics Uncertainty principle …   Wikipedia Chaotic Inflation theory — Physical cosmology Universe · Big Bang …   Wikipedia BKS theory — The Bohr Kramers Slater (BKS) theory [N. Bohr, Collected Works, J. Kalckar, ed. North Holland, Amsterdam, etc., 1985, Vol. 5, pp. 3 216.] [J. Mehra and H. Rechenberg, The historical development of quantum theory, Springer Verlag, New York, etc.,… …   Wikipedia 18+ © Academic, 2000-2024 Contact us: Technical Support, Advertising Dictionaries export, created on PHP, Joomla, Drupal, WordPress, MODx. Mark and share Search through all dictionaries Translate… Search Internet Share the article and excerpts Direct link … Do a right-click on the link above and select “Copy Link”