20161220 Semidefinite Programming Relaxation

Ce cours de niveau master/doctorat présente la technique de relaxation par programmation semi-définie (SDP) comme méthode d’approximation pour des problèmes d’optimisation combinatoire NP-difficiles. L’exposé commence par un rappel de la programmation linéaire et entière, puis introduit le concept de relaxation (passer de variables entières à réelles). L’accent est mis sur le problème Max Cut : maximiser le nombre d’arêtes traversant une bipartition. L’enseignant explique historiquement l’avènement de la SDP en 1994 avec l’algorithme de Goemans et Williamson qui atteint un facteur d’approximation de 1.138…, bien meilleur que les précédents facteurs 2. La démarche comporte trois étapes : (1) formuler le problème comme une programmation quadratique en variables binaires ±1, (2) relâcher les variables en vecteurs unitaires de haute dimension, puis reformuler en une matrice semi-définie positive, (3) résoudre le problème SDP avec un algorithme polynomial, puis extraire une solution entière par un arrondi aléatoire utilisant un hyperplan. La preuve d’approximation est évoquée mais non détaillée faute de temps. L’enseignant relie cette technique au Support Vector Machine, également basé sur le plongement en haute dimension. Le cours encourage les étudiants à comprendre la beauté mathématique de la méthode.