Utilisation des variétés polaires pour la résolution de problèmes d'optimisation

par Aurélien Greuet (Université de Versailles et Équipe SALSA/INRIA/LIP6/UPMC)

jeudi 13 oct. 2011, 10:30 → 11:30 Europe/Paris

XR.203 (Bâtiment XLIM)

On considère des problèmes d'optimisation globale algébrique : il s'agit de calculer la borne inférieure f* d'un polynôme f à plusieurs variables sous des contraintes polynomiales. Résoudre un tel problème peut avoir plusieurs significations selon le contexte applicatif. On peut chercher à obtenir un codage algébrique (polynôme à une variable et intervalle d'isolation) afin d'éviter les problèmes d'approximations. On peut aussi, à l'aide de décompositions en sommes de carrés de polynômes, chercher à obtenir des bornes inférieures certifiées sur f*. Enfin, dans plusieurs applications, en particulier pour l'utilisation du calcul numérique, il est intéressant de savoir si f* est atteint ou pas. Dans cet exposé, on s'intéresse aux propriétés des variétés polaires, définies comme lieux critiques de projections sur des sous-espaces linéaires. Leurs propriétés sont utiles pour résoudre les problèmes précédents. Dans un premier temps, nous les utiliserons pour l'optimisation sous des contraintes polynomiales. Nous verrons comment améliorer le calcul numérique de décomposition en sommes de carrés, puis comment obtenir un algorithme de calcul formel pour calculer f*. Dans un second temps, nous verrons comment utiliser les variétés polaires pour décider, dans le cas non contraint, si f* est atteint. Certains de ces travaux sont communs avec M. Safey El Din; d'autres sont communs avec F. Guo, M. Safey El Din et L. Zhi.