Du transport optimal et de son application en apprentissage statistique
Introduction
Le problème du transport optimal peut être motivé par une situation bien française : chaque matin à Paris, quelques 1300 boulangeries doivent approvisionner en croissants les 2000 cafés de la ville. Il s’agit de le faire d’une manière qui a du sens. On veut transporter optimalement les croissants des boulangeries vers les cafés. Nous allons formaliser un peu tout cela :
Supposons que nous avons \(b_n\) la production en croissant de la \(n\)-ième boulangerie et \(c_n\) la demande en café du nième café. De plus, pour chaque couple boulangerie-café on a un coût \(c_{\,\text{boulangerie } \rightarrow \text{ café}}\) qui correspond au temps de transport pour déplacer un croissant de cette boulangerie à ce café.
Le problème du transport optimal consiste à trouver un plan de transport qui associe à chaque boulangerie les cafés qu’elle doit livrer, et qui minimise le temps de transport total de ces croissants dans Paris.
Issue d’un problème assez simple, la théorie du transport optimal a eu de nombreuses répercussions, que ce soit en mathématiques, en physique ou en économie. Porté par Monge au XVIII siècle, puis par Kantorovich au XX siècle, le domaine a connu un nouvel essor avec la contribution récente de Villani et les applications nouvellement trouvées dans le domaine de l’intelligence artificielle.
Ce mémoire s’appliquera à exposer les bases théoriques du problème du transport optimal et proposera un tour d’horizon des méthodes numériques qui permettent en pratique de le résoudre. Enfin nous présenterons deux exemples issus de la recherche de son application dans le domaine de l’apprentissage statistique.