Quelques applications géométriques de la programmation semidéfinie positive
L’idée d’utiliser la programmation semidéfinie positive pour donner une valeur approchée du nombre d’indépendance d’un graphe est due à Lovász dans son article fondateur de 1979. Depuis lors, les applications de cette méthode d’optimisation convexe se sont développées dans plusieurs directions, et en particulier, combinée à des outils d’analyse harmonique, dans le contexte de problèmes géométriques. Des progrès importants ont ainsi pu être obtenus sur des problèmes de géométrie classique comme ceux du nombre de contacts, de l’empilement des sphères, ou du nombre chromatique de l’espace Euclidien.
Dans cet exposé, nous expliquerons d’abord l’idée de la méthode dans le contexte unificateur des graphes finis, puis nous discuterons ses généralisations aux questions géométriques mentionnées précédemment. Enfin, nous aborderons quelques développements récents visant à raffiner cette méthode dans l’esprit des hiérarchies étudiées en optimisation combinatoire.
-
Téléchargements
-
-
Liens