Mixed complementarity problem

Short description: Formulation in mathematical programming

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):{\mathbb{ℝ}}^n\to {\mathbb{ℝ}}^n$, lower values ${\ell }_i\in \mathbb{ℝ}\cup \{-\mathrm{\infty }\}$ and upper values $u_i\in \mathbb{ℝ}\cup \{\mathrm{\infty }\}$, with $i\in \{1,\dots ,n\}$.

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

• $x_i={\ell }_i,F_i(x)\ge 0$;
• ${\ell }_i<x_i<u_i,F_i(x)=0$;
• $x_i=u_i,F_i(x)\le 0$.

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

See also

• Complementarity theory

References

• Stephen C. Billups (1995). "Algorithms for complementarity problems and generalized equations" (PS). https://ftp.cs.wisc.edu/math-prog/tech-reports/95-14.ps. Retrieved 2006-08-14. 
• Francisco Facchinei, Jong-Shi Pang (2003). Finite-Dimensional Variational Inequalities and Complementarity Problems, Volume I.