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

The mixed complementarity problem is defined by a mapping F ( x ) : R n → R n {\displaystyle F(x):\mathbb {R} ^{n}\to \mathbb {R} ^{n}} , lower values ℓ i ∈ R ∪ { − ∞ } {\displaystyle \ell _{i}\in \mathbb {R} \cup \{-\infty \}} and upper values u i ∈ R ∪ { ∞ } {\displaystyle u_{i}\in \mathbb {R} \cup \{\infty \}} , with i ∈ { 1 , … , n } {\displaystyle i\in \{1,\ldots ,n\}} .

The solution of the MCP is a vector x ∈ R n {\displaystyle x\in \mathbb {R} ^{n}} such that for each index i ∈ { 1 , … , n } {\displaystyle i\in \{1,\ldots ,n\}} one of the following alternatives holds:

• x i = ℓ i , F i ( x ) ≥ 0 {\displaystyle x_{i}=\ell _{i},\;F_{i}(x)\geq 0} ;
• ℓ i < x i < u i , F i ( x ) = 0 {\displaystyle \ell _{i}<x_{i}<u_{i},\;F_{i}(x)=0} ;
• x i = u i , F i ( x ) ≤ 0 {\displaystyle x_{i}=u_{i},\;F_{i}(x)\leq 0} .

Another definition for MCP is: it is a variational inequality on the parallelepiped [ ℓ , u ] {\displaystyle [\ell ,u]} .

• Complementarity theory

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