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

The mixed complementarity problem is defined by a mapping $F (x) : ℝ^{n} \to ℝ^{n}$ , lower values $ℓ_{i} \in ℝ \cup {- \infty}$ and upper values $u_{i} \in ℝ \cup {\infty}$ , with $i \in {1, \dots, n}$ .

The solution of the MCP is a vector $x \in ℝ^{n}$ such that for each index $i \in {1, \dots, n}$ one of the following alternatives holds:

$x_{i} = ℓ_{i}, F_{i} (x) \geq 0$ ;
$ℓ_{i} < x_{i} < u_{i}, F_{i} (x) = 0$ ;
$x_{i} = u_{i}, F_{i} (x) \leq 0$ .

Another definition for MCP is: it is a variational inequality on the parallelepiped $[ℓ, u]$ .

References

Stephen C. Billups (1995). "Algorithms for complementarity problems and generalized equations" (PS). Retrieved 2006-08-14.
Francisco Facchinei, Jong-Shi Pang (2003). Finite-Dimensional Variational Inequalities and Complementarity Problems, Volume I.

v t e Complementarity problems and algorithms
Complementarity Problems	Linear programming (LP) Quadratic programming (QP) Linear complementarity problem (LCP) Mixed linear (MLCP) Mixed (MCP) Nonlinear (NCP)
Basis-exchange algorithms	Simplex (Dantzig) Revised simplex Criss-cross Lemke

Mixed complementarity problem

Definition

See also

References