Quelques contributions en optimisation dans l’incertain et optimisation robuste

Vendredi 18 mai 2018, 13h45, D 102

Olivier Spanjaard, Université Pierre et Marie Curie

Après avoir brièvement rappelé les principaux enjeux de la théorie de la décision algorithmique, nous présenterons dans la première partie de l’exposé quelques résultats récents sur l’optimisation de critères alternatifs à l’espérance d’utilité en décision séquentielle dans l’incertain. Plus précisément, nous montrerons que la détermination d’une politique optimale au sens d’une fonction d’utilité bilinéaire antisymétrique est NP-difficile, mais que le problème devient de complexité polynomiale si on se restreint au modèle de l’utilité espérée pondérée. La seconde partie de l’exposé portera sur l’optimisation robuste avec données intervalles. Plus précisément, nous présenterons une procédure générique de calcul d’une borne inférieure du minimax regret. Cette borne inférieure est calculée à l’aide d’un algorithme de double oracle (qui peut être vu comme une méthode de génération de colonnes et de contraintes en programmation mathématique). Cette méthode peut être implantée efficacement pour tout problème d’optimisation combinatoire robuste dont la variante classique est "facile".