Complémentarité

Le problème de complémentarité linéaire consiste à trouver un vecteur ${\displaystyle x\in \mathbb {R} ^{n}}$ tel que

${\displaystyle x\geqslant 0,\qquad Mx+q\geqslant 0\qquad {\mbox{et}}\qquad \langle x,Mx+q\rangle =0,}$

où ${\displaystyle M\in \mathbb {R} ^{n\times n}}$, ${\displaystyle q\in \mathbb {R} ^{n}}$ et ${\displaystyle \langle \cdot ,\cdot \rangle }$ désigne le produit scalaire euclidien. Les inégalités doivent se comprendre composante par composante. On écrit souvent ce problème de manière concise comme suit :

${\displaystyle 0\leqslant x\perp (Mx+q)\geqslant 0.}$

La relation d'orthogonalité ${\displaystyle \langle x,Mx+q\rangle =0}$ peut se réaliser de ${\displaystyle 2^{n}}$ manières différentes : pour tout ${\displaystyle i\in [\![1,n]\!]}$, soit ${\displaystyle x_{i}=0}$, soit ${\displaystyle (Mx+q)_{i}=0}$. C'est ce grand nombre de possibilité qui rend le problème difficile à résoudre. Il est le plus souvent NP-difficile.

Un problème de complémentarité plus général, et non linéaire, consiste à trouver un vecteur ${\displaystyle x}$ dans un ensemble ${\displaystyle \mathbb {E} }$ tel que

${\displaystyle K\ni F(x)\perp G(x)\in K^{+},}$

où ${\displaystyle F:\mathbb {E} \to \mathbb {H} }$ (${\displaystyle \mathbb {H} }$ est un espace de Hilbert), ${\displaystyle G:\mathbb {E} \to \mathbb {H} }$, ${\displaystyle K}$ est un cône convexe fermé non vide de ${\displaystyle \mathbb {H} }$, ${\displaystyle K^{+}}$ est le cône dual positif de ${\displaystyle K}$ et l'orthogonalité est prise au sens du produit scalaire de ${\displaystyle \mathbb {H} }$. Cette écriture signifie que l'on cherche ${\displaystyle x\in \mathbb {E} }$ tel que ${\displaystyle F(x)\in K}$, ${\displaystyle G(x)\in K^{+}}$ et tel que ${\displaystyle F(x)}$ et ${\displaystyle G(x)}$ soient orthogonaux.

• Complémentarité linéaire
• Inéquation variationnelle

• (en) S. C. Billups, K. G. Murty (2000), « Complementarity problems », Journal of Computational and Applied Mathematics, 124, 303–318.
• (en) F. Facchinei, J.-S. Pang (2003), Finite-Dimentional Variational Inequalities and Complementarity Problems (2 tomes), Springer Series in Operations Research, Springer-Verlag, New York.

• Portail des mathématiques