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

i

: 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 ...

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 philosoph ...

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 ...

References

External links

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

History

See also

References

Further reading

Collections

External links