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 [math]\displaystyle{ F(x): \mathbb{R}^n \to \mathbb{R}^n }[/math], lower values [math]\displaystyle{ \ell_i \in \mathbb{R} \cup \{-\infty\} }[/math] and upper values [math]\displaystyle{ u_i \in \mathbb{R}\cup\{\infty\} }[/math].

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

• [math]\displaystyle{ x_i = \ell_i, \; F_i(x) \ge 0 }[/math];
• [math]\displaystyle{ \ell_i \lt x_i \lt u_i, \; F_i(x) = 0 }[/math];
• [math]\displaystyle{ x_i = u_i, \; F_i(x) \le 0 }[/math].

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

See also

• Complementarity theory

References

• Stephen C. Billups (1995). [https:/ftp.cs.wisc.edu/math-prog/tech-reports/95-14.ps "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.