1 Le problème du transport optimal
1.1 Le problème selon Kantorovitch
1.1.1 Formulation générale
Soit
Remarque 1.1. L’hypothèse importante est que les mesures soient de même masse totale finie (conservation de la masse lors du transport).
Le problème de Monge-Kantorovitch est une version relaxée et symétrisée par Kantorovitch du problème du transport optimal de Monge (dans le sens où l’on peut fractionner la masse d’un point de la distribution initiale). Il se formule de la manière suivante :
Définition 1.1 (Problème de Monge-Kantorovitch)
Le problème se comprend en interprétant
1.1.2 Formulation discrète
Si
Cette remarque est fondamentale car elle permet d’identifier le problème de Monge-Kantorovitch au problème d’optimisation linéaire (i.e. de minimisation d’une forme linéaire sur un polytope convexe en dimension finie) suivant :
Remarque 1.2. Cette traduction du problème dans sa version discrète est principalement introduite en raison de sa forme matricielle qui se prête bien aux méthodes d’optimisation linéaire de la Section 1.2 et aux algorithmes de résolution qui seront présentés au Chapitre 2.
1.1.3 Existence des solutions
Proposition 1.1 (Existence des solutions) Le problème de Monge-Kantorovitch admet des solutions, i.e. il existe au moins un couplage optimal
Preuve. Dans le cas où
1.2 Dualité lagrangienne
Le déroulement naturel est alors d’introduire le lagrangien, afin de libérer les contraintes affines :
Définition 1.2 Le lagrangien
Alors on peut réécrire le problème discret sous la forme :
Le problème dual apparaît lors de l’inversion entre
Or on a :
Ainsi :
Cette équation peut se réécrire dans le formalisme du problème initial dans le cas où les mesures sont à support fini :
Définition 1.3 (Problème de Monge-Kantorovitch, énoncé dual)
Remarque 1.3. La régularité des potentiels
Théorème 1.1 (Dualité faible, dualité forte)
- (Dualité faible).
- (Dualité forte).
Preuve. On exposera la preuve dans le cas où les mesures sont à support fini. La dualité générale est démontrée par Villani (2009).
(Dualité faible). Celle-ci découle simplement du fait que le plus grand des minima est inférieur au plus petit des maxima.
(Dualité forte). La dualité forte se démontre en suivant l’algorithme du simplexe, ou via le lemme de Farkas, qui se déduit du théorème de séparation point/convexe-fermé par des hyperplans. C’est un résultat général pour tous les problèmes d’optimisation linéaire admettant une solution.