Complémentarité

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Article connexe : Complémentaire.

En mathématiques, un problème de complémentarité est un système d'équations et d'inéquations, contenant une relation d'orthogonalité qui induit une combinatoire importante dans ce système, c'est-à-dire un grand nombre de manières de réaliser cette orthogonalité par des équations. La complémentarité est la discipline qui analyse ces problèmes et propose des algorithmes de résolution.

Les problèmes de complémentarité peuvent souvent être vu comme des cas particuliers d'inéquations variationnelles.

Exemples de problèmes de complémentarité[modifier | modifier le code]

Complémentarité linéaire[modifier | modifier le code]

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


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

M\in\R^{n\times n}, q\in\R^n et \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 :


0\leqslant x\perp(Mx+q)\geqslant 0.

La relation d'orthogonalité \langle x, Mx+q \rangle=0 peut se réaliser de 2^n manières différentes : pour tout i\in[\![1,n]\!], soit x_i=0, soit (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 ardu (en).

Généralisation[modifier | modifier le code]

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


K\ni F(x) \perp G(x)\in K^+,

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

Annexes[modifier | modifier le code]

Articles connexes[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (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.