Séminaire de Géométrie Tropicale
Mercredi 23 mars 2016 14h salle 1525-502
Xavier Allamigeon
(INRIA et CMAP, École Polytechnique, CNRS)
Résumé :
Le chemin central est la trajectoire approximativement suivie par les techniques dites de points intérieurs en optimisation convexe. La complexité de ces algorithmes est donc relié à la forme du chemin central, ce qui a motivé plusieurs travaux et conjectures sur la courbure du chemin central. Nous proposons d'étudier le chemin central en programmation linéaire à travers sa tropicalisation. Nous obtenons une caractérisation géométrique du chemin central tropical, et en déduisons une famille de chemins centraux exhibant des propriétés inattendues. Nous établissons ainsi des résultats sur leur courbure, et plus concrètement sur la complexité des techniques de points intérieurs.
Cet exposé s'appuie sur un travail mené conjointement avec P. Benchimol (EDF R&D), S. Gaubert (INRIA et CMAP, Ecole Polytechnique, CNRS) et M. Joswig (TU Berlin).