Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Complémentarité linéaire
Résumé
En mathématiques, et plus spécialement en recherche opérationnelle et en optimisation, un problème de complémentarité linéaire est défini par la donnée d'une matrice et d'un vecteur et consiste à trouver un vecteur tel que ses composantes et celles de soient positives et tel que x et y soient orthogonaux pour le produit scalaire euclidien de :
où désigne le vecteur x transposé. Ce problème peut être vu comme un cas particulier d'inéquation variationnelle.
Ces problèmes sont souvent NP-difficiles et donc difficiles à résoudre lorsque la dimension du problème devient grande. La combinatoire du problème vient du fait qu'il faut déterminer quelles sont les composantes de la solution qui sont nulles et il y a 2 possibilités de réaliser cela.
Les problèmes de complémentarité se sont d'abord manifestés dans les conditions d'optimalité des problèmes d'optimisation, les conditions de Karush, Kuhn et Tucker. Elles permettent de modéliser des problèmes décrits par plusieurs systèmes d'équations qui sont en quelque sorte en compétition ; celui qui est actif en un endroit et temps donnés, correspondant à un indice commun de x et de y, dépend de seuils qui sont ou non atteints : si le seuil n'est pas atteint, c'est-à-dire que , l'équation est active. Les exemples de problèmes modélisés par complémentarité sont nombreux : problèmes de contact, problèmes d'apparition et de disparition de phases dans les écoulements multiphasiques, problèmes de précipitation-dissolution en chimie, en météorologie, etc.
Pour un vecteur , la notation signifie que toutes les composantes du vecteur sont positives ou nulles.
On note l'orthant positif de .
Pour deux parties A et B d'un espace vectoriel, désigne leur somme de Minkowski, qui est l'ensemble .
Étant donnés une matrice réelle carrée , non nécessairement symétrique, et un vecteur , un problème de complémentarité linéaire consiste à trouver un vecteur tel que
Le symbole ci-dessus est utilisé pour désigner la transposition du vecteur à sa gauche.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.