Complementarity theory explained
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 vectors must equal zero, i.e. they are orthogonal.[1] In particular for finite-dimensional real vector spaces this means that, if one has vectors X and Y with all nonnegative components (xi ≥ 0 and yi ≥ 0 for all
: in the
first quadrant if 2-dimensional, in the first
octant if 3-dimensional), then for each pair of components
xi and
yi 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 theoryinclude: optimization, equilibrium problems, variational inequality theory, fixed point theory, topological degree theory and nonlinear analysis.
See also
References
- Billups . Stephen . Murty . Katta . Complementarity Problems . 10.1016/S0377-0427(00)00432-5. 2000 . Journal of Computational and Applied Mathematics . 124 . 1–2 . 303–318. 2000JCoAM.124..303B . free .
Further reading
- Book: Richard W. Cottle . Jong-Shi Pang . Richard E. Stone . The Linear Complementarity Problem . . 1992 . 978-0-12-192350-1.
- Book: George Isac . Complementarity Problems . Springer . 1992 . 978-3-540-56251-1.
- Book: George Isac . Topological Methods in Complementarity Theory . Springer . 2000 . 978-0-7923-6274-6.
- Book: Francisco Facchinei . Jong-Shi Pang . Finite-Dimensional Variational Inequalities and Complementarity Problems: v.1 and v.2 . Springer . 2003 . 978-0-387-95580-3.
- Book: Murty, K. G. . Linear complementarity, linear and nonlinear programming . Sigma Series in Applied Mathematics . 3 . Heldermann Verlag . Berlin . 1988 . xlviii+629 pp . 3-88538-403-5 . 949214 . dead . https://web.archive.org/web/20100401043940/http://ioe.engin.umich.edu/people/fac/books/murty/linear_complementarity_webbook/ . 2010-04-01 .
Collections
- Book: Richard Cottle . F. Giannessi . Jacques Louis Lions . Variational Inequalities and Complementarity Problems: Theory and Applications . . 1980 . 978-0-471-27610-4.
- Book: Michael C. Ferris . Jong-Shi Pang . Complementarity and Variational Problems: State of the Art . . 1997 . 978-0-89871-391-6.
External links
