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 criterion, from some set of available alternatives. It is generally divided into two subfi ...
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 space, Hausdorff pre-Hilbert space) is a real vector space or a complex vector space with an operation (mathematics), operation called an inner product. The inner product of two ve ...
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
A Cartesian coordinate system (, ) in a plane is a coordinate system that specifies each point uniquely by a pair of numerical coordinates, which are the signed distances to the point from two fixed perpendicular oriented lines, measured in t ...
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 In mathematics, a variational inequality is an inequality involving a functional, which has to be solved for all possible values of a given variable, belonging usually to a convex set. The mathematical theory of variational inequalities was initial ...
.
History
Complementarity problems were originally studied because the
Karush–Kuhn–Tucker conditions
In mathematical optimization, the Karush–Kuhn–Tucker (KKT) conditions, also known as the Kuhn–Tucker conditions, are first derivative tests (sometimes called first-order necessary conditions) for a solution in nonlinear programming to be o ...
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 are represented by linear function#As a polynomial function, li ...
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 constra ...
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 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 ...
(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 philosophe ...
showed that, for two person games, computing a
Nash equilibrium
In game theory, the Nash equilibrium, named after the mathematician John Nash, is the most common way to define the solution of a non-cooperative game involving two or more players. In a Nash equilibrium, each player is assumed to know the equili ...
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 descr ...
s. Since then the study of complementarity problems and variational inequalities has expanded enormously.
Areas of
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
and
science
Science is a systematic endeavor that builds and organizes knowledge in the form of testable explanations and predictions about the universe.
Science may be as old as the human species, and some of the earliest archeological evidence for ...
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
In mathematics, a fixed-point theorem is a result saying that a function ''F'' will have at least one fixed point (a point ''x'' for which ''F''(''x'') = ''x''), under some conditions on ''F'' that can be stated in general terms. Some authors cla ...
,
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 solution ...
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