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): \mathbb{R}^n \to \mathbb{R}^n$ , lower values $\ell_i \in \mathbb{R} \cup \{-\infty\}$ and upper values $u_i \in \mathbb{R}\cup\{\infty\}$ .

The solution of the MCP is a vector $x \in \mathbb{R}^n$ such that for each index $i \in \{1, \ldots, 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]$ .

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.

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

This article is issued from Wikipedia - version of the Saturday, March 16, 2013. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Mixed complementarity problem

Definition

See also

References