A complementarity problem is a type of
mathematical optimization 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
*Vector (epidemiology), an agent that carries and transmits an infectious pathogen into another living organism
Vector may also refer to:
Mathematic ...
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, often ...
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
: 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
Quadratic programming (QP) is the process of solving certain mathematical optimization problems involving quadratic functions. Specifically, one seeks to optimize (minimize or maximize) a multivariate quadratic function subject to linear constr ...
constitute a
linear complementarity problem In mathematical optimization theory, the linear complementarity problem (LCP) arises frequently in computational mechanics and encompasses the well-known quadratic programming as a special case. It was proposed by Cottle and Dantzig in 1968. ...
(LCP) or a
mixed complementarity problem (MCP). In 1963
Lemke and
Howson Howson is a surname. Notable people with the surname include:
* Howson family, show business dynasty
* Albert Howson (1881–1960), American actor
* Charles Howson (1896–1976), English footballer
* Colin Howson (1945–2020), British philosoph ...
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 game In game theory, a bimatrix game is a simultaneous game for two players in which each player has a finite number of possible actions. The name comes from the fact that the normal form of such a game can be described by two matrices - matrix A descri ...
s. Since then the study of complementarity problems and variational inequalities has expanded enormously.
Areas of
mathematics and
science
Science is a systematic endeavor that Scientific method, builds and organizes knowledge in the form of Testability, testable explanations and predictions about the universe.
Science may be as old as the human species, and some of the earli ...
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 criterion, from some set of available alternatives. It is generally divided into two subfi ...
,
equilibrium problems,
variational inequality theory,
fixed point theory,
topological degree theory In mathematics, topological degree theory is a generalization of the winding number of a curve in the complex plane. It can be used to estimate the number of solutions of an equation, and is closely connected to fixed-point theory. When one solutio ...
and
nonlinear analysis
Nonlinear functional analysis is a branch of mathematical analysis that deals with nonlinear mappings.
Topics
Its subject matter includes:
* generalizations of calculus to Banach spaces
* implicit function theorems
* fixed-point theorems (Br ...
.
See also
*
Mathematical programming with equilibrium constraints Mathematical programming with equilibrium constraints (MPEC) is the study of
constrained optimization problems where the constraints include variational inequalities or complementarities. MPEC is related to the Stackelberg game.
MPEC is used ...
*
nl format for representing complementarity problems
References
Further reading
*
*
*
*
*
Collections
*
*
External links
CPNET:Complementarity Problem Net
Mathematical optimization
Functional analysis
Topology
{{mathanalysis-stub