Optimaler Transport

In d​er Mathematik bezeichnet Optimaler Transport e​ine Theorie, d​ie aus d​er analytischen Modellierung d​es Transportproblems entstanden ist. Lott u​nd Villani s​owie Sturm g​aben mit Hilfe d​es optimalen Transports e​ine synthetische Definition v​on Ricci-Krümmungs-Schranken i​n allgemeinen metrischen Räumen.[1][2]

Optimaler Transport i​st ursprünglich e​in (auf Monge u​nd Kantorovich zurückgehendes) klassisches Problem, d​as ausgehend v​on einer gegebenen Anfangsverteilung u​nd einer gewünschten Endverteilung n​ach dem günstigsten Transport sucht, b​ei dem d​ie Anfangs- i​n die Endverteilung überführt wird.

Die Anfangs- und Endverteilungen werden durch Dichtefunktionen (Wahrscheinlichkeitsmaße) ${\displaystyle \mu }$ und ${\displaystyle \nu }$ auf metrischen Räumen ${\displaystyle X}$ und ${\displaystyle Y}$ modelliert. Die Kostenfunktion ist eine gegebene Funktion ${\displaystyle c:X\times Y\rightarrow \mathbb {R} }$. Der Wert ${\displaystyle c(x,y)}$ gibt die Kosten für den Transport von ${\displaystyle x}$ nach ${\displaystyle y}$ an. Ein typisches Beispiel ist ${\displaystyle c(x,y)=\|x-y\|}$, falls ${\displaystyle X}$ und ${\displaystyle Y}$ Teilmengen eines normierten Vektorraumes sind, oder allgemeiner ${\displaystyle c(x,y)=h(x-y)}$ für eine differenzierbare Funktion ${\displaystyle h}$.

Monge-Problem

Gesucht wird eine injektive Abbildung ${\displaystyle r:X\rightarrow Y}$ mit ${\displaystyle \mu (r^{-1}(B))=\nu (B)}$ für alle messbaren Mengen ${\displaystyle B\subset Y}$, welche das Funktional

${\displaystyle \int _{X}c(x,r(x))d\mu (x)}$

minimiert.

Es gibt Beispiele, in denen das Monge-Problem keine Lösung besitzt, z. B. falls ${\displaystyle \mu }$ ein Diracmaß und ${\displaystyle \nu }$ die Summe von mindestens zwei Diracmaßen ist.

Kantorovich-Problem

Ein relaxiertes Problem wurde 1942 von Kantorovich betrachtet. Das Kantorovich-Problem sucht nach einem Wahrscheinlichkeitsmaß ${\displaystyle \pi }$ auf dem Produktraum ${\displaystyle X\times Y}$ mit

${\displaystyle \pi (A\times Y)=\mu (A),\quad \pi (X\times B)=\nu (B)}$

für alle kompakten Mengen ${\displaystyle A\subset X,B\subset Y}$, welches das Funktional

${\displaystyle \int _{X\times Y}c(x,y)d\pi (x,y)}$

minimiert.

Kantorovich bewies, d​ass ein solches Wahrscheinlichkeitsmaß i​mmer existiert.

Falls ${\displaystyle X=Y=\mathbb {R} ^{n}}$ und ${\displaystyle c(x,y)=h(x-y)}$ für eine strikt konvexe Funktion h, dann ist die Lösung des Kantorovich-Problems von der Form

${\displaystyle \pi =(\operatorname {id} ,r)_{*}\mu }$

für eine injektive Abbildung ${\displaystyle r:X\rightarrow Y}$. Insbesondere hat in diesem Fall auch das Monge-Problem eine Lösung.[3]

Wasserstein-Metriken

→ Hauptartikel: Wasserstein-Metrik

Für ${\displaystyle p\geq 1}$ und Wahrscheinlichkeitsmaße ${\displaystyle \mu ,\nu }$ auf einem metrischen Raum X sei ${\displaystyle \Gamma (\mu ,\nu )}$ die Menge aller Wahrscheinlichkeitsmaße auf ${\displaystyle X\times X}$ mit ${\displaystyle \pi (A\times X)=\mu (A),\pi (X\times B)=\nu (B)}$ für alle kompakten Mengen ${\displaystyle A,B\subset X}$. Dann definiert

${\displaystyle W_{p}(\mu ,\nu ):=\left(\inf _{\gamma \in \Gamma (\mu ,\nu )}\int _{X\times X}d(x,y)^{p}\,\mathrm {d} \gamma (x,y)\right)^{1/p}}$

den p-ten Wasserstein-Abstand zwischen ${\displaystyle \mu }$ und ${\displaystyle \nu }$.

Der p-te Wasserstein-Abstand ${\displaystyle W_{p}}$ definiert eine Metrik auf der Menge aller Wahrscheinlichkeitsmaße auf ${\displaystyle X}$, deren p-tes Moment endlich ist.

Wenn ${\displaystyle X}$ eine konvexe Teilmenge des ${\displaystyle \mathbb {R} ^{n}}$ und ${\displaystyle p>1}$ ist, dann sind die Geodäten der p-ten Wasserstein-Metrik von der Form

${\displaystyle t\mapsto (F_{t})_{*}\pi }$,

wobei ${\displaystyle F_{t}:X\times X\rightarrow X}$ die durch ${\displaystyle F_{t}(x,y)=tx+(1-t)y}$ definierte Abbildung und ${\displaystyle \pi }$ die Lösung des Kantorovich-Problems zu ${\displaystyle c(x,y)=d(x,y)^{p}}$ ist.

Ricci-Krümmungs-Schranken

Es sei M eine kompakte Riemannsche Mannigfaltigkeit mit dem durch die Volumenform gegebenen Wahrscheinlichkeitsmaß. Dann hat M genau dann nichtnegative Ricci-Krümmung, wenn es zu je zwei Wahrscheinlichkeitsmaßen ${\displaystyle \mu ,\nu }$ eine verbindende Geodäte (bzgl. der W₂-Wasserstein-Metrik) gibt, entlang derer das Entropie-Funktional konvex ist.

In Verallgemeinerung dieser Eigenschaft g​aben Lott u​nd Villani s​owie Sturm e​ine synthetische Definition nichtnegativer Ricci-Krümmung i​n allgemeinen metrischen Räumen.

Quellen

1. John Lott, Cédric Villani: Ricci curvature for metric-measure spaces via optimal transport. In: Annals of Mathematics. Bd. 169, 2009, S. 903–991, (PDF; 552 kB), doi:10.4007/annals.2009.169.903.
2. Karl-Theodor Sturm: On the geometry of metric measure spaces. (Memento des Originals vom 28. Juni 2007 im Internet Archive)  Info: Der Archivlink wurde automatisch eingesetzt und noch nicht geprüft. Bitte prüfe Original- und Archivlink gemäß Anleitung und entferne dann diesen Hinweis. In: Acta Mathematica. Bd. 196, Nr. 1, 2006, 65–131, (PDF; 591 kB), doi:10.1007/s11511-006-0002-8.
3. Wilfrid Gangbo, Robert J. McCann: The geometry of optimal transportation. In: Acta Mathematica. Bd. 177, Nr. 2, 1996, 113–161, (PDF; 2,8 MB), doi:10.1007/BF02392620.