Le transport optimal

Un plan γ_ij dit quelle quantité part du site i vers le site j. Les seules contraintes sont les marges : ∑_j γ_ij = μ_i et ∑_i γ_ij = ν_j. Minimiser ∑ c_ij γ_ij est un programme linéaire — donc soluble, et surtout muni d'un dual : trouver des prix u_i, v_j avec u_i + v_j ≤ c_ij qui maximisent ∑ u_iμ_i + ∑ v_jν_j. Un transporteur concurrent facture l'enlèvement u_i et la livraison v_j : il ne peut jamais faire payer plus que le trajet direct, et à l'optimum il facture exactement autant.

Ici, sur une droite et pour un coût convexe, l'optimum a une forme explicite : la règle du coin nord-ouest. On sert les sites de gauche à droite, sans jamais croiser. Les cellules actives forment un escalier de m + n − 1 cases, sur lequel les prix se propagent de proche en proche.

Le tableau des coûts réduits c_ij − u_i − v_j est le certificat : toutes les cases positives ou nulles, et nulles exactement là où passe la marchandise. Aucune amélioration n'est possible — la preuve tient dans un tableau.

En dimension 1 tout se calcule : W₁ est exactement l'aire comprise entre les deux fonctions de répartition, et W_p la distance L^p entre les fonctions quantiles. Pour deux gaussiennes, W₂² = (m₁ − m₂)² + (σ₁ − σ₂)².

La courbe du bas explique l'engouement : quand on éloigne deux bosses, la distance L² (et la variation totale, et la divergence de Kullback–Leibler) sature dès qu'elles ne se recouvrent plus — elles disent seulement « différentes », sans mesurer de combien. W₂ croît linéairement avec le décalage : elle garde la géométrie de l'espace sous-jacent. C'est pourquoi elle sert à comparer des images, des nuages de points ou des distributions apprises.

On remplace le coût par ∑ c_ijγ_ij − ε H(γ). La solution prend alors la forme γ = diag(a) K diag(b) avec K_ij = e^−c_ij/ε, et il ne reste qu'à ajuster alternativement les deux vecteurs pour respecter chaque marge : c'est l'algorithme de Sinkhorn–Knopp, deux produits matrice-vecteur par itération.

Le prix à payer se voit à l'œil : le plan s'épaissit. Petit ε, plan net mais convergence lente et risque de dépassement numérique ; grand ε, convergence immédiate et transport flou qui surestime la distance. Ce compromis, et le fait que l'algorithme soit dérivable, ont fait entrer le transport optimal dans l'apprentissage automatique.

Les deux courbes partent de μ et arrivent à ν. Entre les deux, tout diffère. Le mélange fait décroître la première bosse et croître la seconde : à mi-chemin, la matière est aux deux endroits à la fois, et jamais entre les deux. Le déplacement transporte chaque quantile en ligne droite : la bosse voyage sans se déformer, et sa variance suit ((1−t)σ₁ + tσ₂)² au lieu d'enfler du terme parasite t(1−t)(m₁ − m₂)².

Cette famille μ_t est la géodésique de l'espace de Wasserstein : W₂(μ, μ_t) = t · W₂(μ, ν), exactement comme un segment dans le plan euclidien. La formulation dynamique de Benamou et Brenier (2000) lit la même chose comme un écoulement de fluide qui minimise son énergie cinétique.

Le théorème de Brenier (1987) referme la boucle ouverte par Monge : pour le coût quadratique, dès que μ n'a pas d'atomes, le plan optimal de Kantorovich est porté par une vraie application, et cette application est le gradient d'une fonction convexe. Le terrassier avait raison, il fallait deux siècles pour le démontrer.