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

)

:

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]}

.

See also

Complementarity theory

References

Stephen C. Billups (1995). "Algorithms for complementarity problems and generalized equations" (PS). Retrieved 2006-08-14.

Francisco Facchinei, Jong-Shi Pang (2003).