A complementarity problem is a type of

mathematical optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...

problem. It is the problem of optimizing (minimizing or maximizing) a function of two

vector Vector most often refers to: * Euclidean vector, a quantity with a magnitude and a direction * Disease vector, an agent that carries and transmits an infectious pathogen into another living organism Vector may also refer to: Mathematics a ...

variables subject to certain requirements (constraints) which include: that the

inner product In mathematics, an inner product space (or, rarely, a Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation called an inner product. The inner product of two vectors in the space is a scalar, ofte ...

of the two vectors must equal zero, i.e. they are orthogonal. In particular for finite-dimensional real vector spaces this means that, if one has vectors ''X'' and ''Y'' with all ''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 Linear programming (LP), also called linear optimization, is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements and objective are represented by linear function#As a polynomia ...

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 In game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed) ...

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 Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

and

science Science is a systematic discipline that builds and organises knowledge in the form of testable hypotheses and predictions about the universe. Modern science is typically divided into twoor threemajor branches: the natural sciences, which stu ...

that contributed to the development of complementarity theory include:

optimization Mathematical optimization (alternatively spelled ''optimisation'') or mathematical programming is the selection of a best element, with regard to some criteria, from some set of available alternatives. It is generally divided into two subfiel ...

, equilibrium problems, variational inequality theory, fixed point theory, topological degree theory and nonlinear analysis.

References

External links

CPNET:Complementarity Problem Net
Mathematical optimization Functional analysis Topology {{mathanalysis-stub

History

See also

References

Further reading

Collections

External links