Optimaler Transport

In der Mathematik bezeichnet Optimaler Transport eine Theorie, die aus der analytischen Modellierung des Transportproblems entstanden ist. Lott und Villani sowie Sturm gaben mit Hilfe des optimalen Transports eine synthetische Definition von Ricci-Krümmungs-Schranken in allgemeinen metrischen Räumen.^[1][2]

Optimaler Transport ist ursprünglich ein (auf Monge und Kantorovich zurückgehendes) klassisches Problem, das ausgehend von einer gegebenen Anfangsverteilung und einer gewünschten Endverteilung nach dem günstigsten Transport sucht, bei dem die Anfangs- in 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, dass ein solches Wahrscheinlichkeitsmaß immer 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

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 gaben Lott und Villani sowie Sturm eine synthetische Definition nichtnegativer Ricci-Krümmung in 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 vom 28. Juni 2007 im Internet Archive) 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.