En analyse convexe, 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 vus comme des cas particuliers d'inéquations variationnelles. Elles se sont d'abord présentées dans les conditions d'optimalité des problèmes d'optimisation sous contraintes, les conditions de Karush, Kuhn et Tucker.

Exemples de problèmes de complémentarité

modifier

Complémentarité linéaire

modifier

Le problème de complémentarité linéaire consiste à trouver un vecteur   tel que

 

 ,   et   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 :

 

La relation d'orthogonalité   peut se réaliser de   manières différentes : pour tout  , soit  , soit  . C'est ce grand nombre de possibilité qui rend le problème difficile à résoudre. Il est le plus souvent NP-difficile.

Complémentarité non linéaire

modifier

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

 

  (  est un espace de Hilbert),  ,   est un cône convexe fermé non vide de  ,   est le cône dual positif de   et l'orthogonalité est prise au sens du produit scalaire de  . Cette écriture signifie que l'on cherche   tel que  ,   et tel que   et   soient orthogonaux.

Annexes

modifier

Articles connexes

modifier

Bibliographie

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