Ecole Polytechnique avril

Cédric Villani

Description

Niveau: Supérieur
TRANSPORT OPTIMAL Ecole Polytechnique, 3 avril 2007 Cedric Villani ENS Lyon & Institut Universitaire de France

• distribution initiale


• probleme des deblais


• formulation moderne


• transport optimal


• finale etant


• remblai


• condition de compatibilite

Sujets

• Leonid Kantorovich
• Institut universitaire de France
• École polytechnique
• Villani
• Terrassement

Informations

• Publié par: zauj
• Publié le: 01 avril 2007
• Nombre de lectures: 66
• Langue: Français

Extrait

TRANSPORT OPTIMAL
´
Ecole Polytechnique, 3 avril 2007
C´edric Villani
ENS Lyon
& Institut Universitaire de FranceGaspard Monge (1746-1818)1781 : Le Probl`eme des d´eblais et remblais
Gaspard Monge consid`ere un probl`eme d’ing´enieur :
transporter de la mati`ere au moindre couˆt, les
distributions initiale et finale ´etant donn´ees
T
x
y
remblais
d´eblaisFormulation moderne
Distribution initiale μ (mesure de probabilit´e)
Distribution finale ν (mesure de probabilit´e)
Construire T : x−→ y =T(x)
Z
P
afin de minimiser c(x,y) = c(x,T(x))dμ(x)
x
Condition de compatibilit´e :
−1
ν[B] = masse totale apport´ee dans B =μ[T (B)]
−1
i.e. ν =T μ =T μ =μ◦T
# ∗
(mesure image ou push-forward)Leonid Vitaliyevich Kantorovich (1912-1986)1942 : Le probl`eme de Kantorovich
μ(dx),ν(dy) deux mesures de probabilit´e
c(x,y)≥ 0 une fonction de couˆt
Z
´
Etudier inf c(x,y)dπ(x,y)
π∈Π(?;ν)
n o
Π(μ,ν) := π(dxdy) dont les marginales sont μ et ν :
∀f,g,
Z Z Z Z
f(x)dπ(x,y) = fdμ, g(y)dπ(x,y) = gdν
Probl`eme de Monge : on ajoute la contrainte
y =T(x), i.e.
π =μ⊗δ , ν =T μ
y=T(x) #Version discr`ete : probl`eme d’appariement optimal
Probl`eme d’appariement de MongeFormulation probabiliste : une “trivialit´e”
´
Etant donn´ees deux variables al´eatoires U et V, de lois
fix´ees a priori, ´etudions inf Ec(U,V) parmi tous les
2
couplages (U,V) possibles (ex. c(U,V) =|U−V| : on
maximise les corr´elations)
Condition de Monge : V =T(U) (couplage d´eterministe)
Formulation analytique : un “monstre”
Supposons μ(dx) =f(x)dx, ν(dy) =g(y)dy
Condition de Monge : T μ =ν
#
f = (g◦T)×|det(DT)|/(multiplicit´e de T)
´equation “fortement non lin´eaire”Applications probabilistes
Pendant des d´ecennies, le probl`eme de
Monge–Kantorovich a ´et´e utilis´e en ´economie,
probabilit´es, statistiques, m´ecanique statistique... en
dimension finie et infinie;
? ?
Z
1/p
p
W (μ,ν) := inf d(x,y) dπ(x,y) (p≥ 1)
p
π∈Π(?;ν)
“m´etrise” la convergence faible des mesures de
probabilit´e (surtout p = 1, p = 2)
Applications : ´etude qualitative de syst`emes de
particules, ´equations diff´erentielles stochastiques,
concentration de la mesure... (Dobrushin, Tanaka,
Sznitman, Marton, Talagrand, Rachev, Ru¨schendorf.....)
(Domaine de recherche actif)Dualit´e de Kantorovich
“Couˆt minimal”←→ “Profit maximal”
Couˆt de transport optimal =
? ?
Z Z
sup ψdν− ϕdμ; ψ(y)−ϕ(x)≤c(x,y)
ϕ : prix d’achat en x
ψ : prix de vente en y
(Exemple concret de dualit´e de programmation lin´eaire)