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.<ref>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), {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}.</ref><ref>Karl-Theodor Sturm: <templatestyles src="Webarchiv/styles.css" />{{#if:20070628202244

      | {{#ifeq: 20070628202244 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: On the geometry of metric measure spaces. | {{#invoke:WLink|getEscapedTitle|On the geometry of metric measure spaces.}} | {{#invoke:Webarchiv|getdomain|http://sfb611.iam.uni-bonn.de/uploads/203-komplett.pdf}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20070628202244}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/DatumDer Wert des Parameters {{#if: wayback | wayback | Datum }} muss ein gültiger Zeitstempel der Form YYYYMMDDHHMMSS sein!
         | {{#if: On the geometry of metric measure spaces. | {{#invoke:WLink|getEscapedTitle|On the geometry of metric measure spaces.}} | {{#invoke:Webarchiv|getdomain|http://sfb611.iam.uni-bonn.de/uploads/203-komplett.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20070628202244}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: On the geometry of metric measure spaces. | {{#invoke:WLink|getEscapedTitle|On the geometry of metric measure spaces.}} | {{#invoke:Webarchiv|getdomain|http://sfb611.iam.uni-bonn.de/uploads/203-komplett.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: On the geometry of metric measure spaces. | {{#invoke:WLink|getEscapedTitle|On the geometry of metric measure spaces.}} | {{#invoke:Webarchiv|getdomain|http://sfb611.iam.uni-bonn.de/uploads/203-komplett.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Der Wert des Parameters {{#if: webciteID | webciteID | ID }} muss entweder ein Zeitstempel der Form YYYYMMDDHHMMSS oder ein Schüsselwert mit 9 Zeichen oder eine 16-stellige Zahl sein!Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: On the geometry of metric measure spaces. | {{#invoke:WLink|getEscapedTitle|On the geometry of metric measure spaces.}} | {{#invoke:Webarchiv|getdomain|http://sfb611.iam.uni-bonn.de/uploads/203-komplett.pdf}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: On the geometry of metric measure spaces. | {{#invoke:WLink|getEscapedTitle|On the geometry of metric measure spaces.}} | {{#invoke:Webarchiv|getdomain|http://sfb611.iam.uni-bonn.de/uploads/203-komplett.pdf}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20070628202244|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|Vorlage:FormatDate/Wartung/Error}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://sfb611.iam.uni-bonn.de/uploads/203-komplett.pdf}}
    || {{#if:  || }} URL/Pfad ungültig.
  }}{{#if: On the geometry of metric measure spaces.
    | {{#if: {{#invoke:WLink|isBracketedLink|On the geometry of metric measure spaces.}}
        | {{#if:  || }} Linktext ungültig.
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt Linktext fehlt.
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://sfb611.iam.uni-bonn.de/uploads/203-komplett.pdf%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://sfb611.iam.uni-bonn.de/uploads/203-komplett.pdf%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://sfb611.iam.uni-bonn.de/uploads/203-komplett.pdf }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} In: Acta Mathematica. Bd. 196, Nr. 1, 2006, 65–131, (PDF; 591 kB), {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}.</ref>

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) <math>\mu</math> und <math>\nu</math> auf metrischen Räumen <math>X</math> und <math>Y</math> modelliert. Die Kostenfunktion ist eine gegebene Funktion <math>c:X\times Y\rightarrow\R</math>. Der Wert <math>c(x,y)</math> gibt die Kosten für den Transport von <math>x</math> nach <math>y</math> an. Ein typisches Beispiel ist <math>c(x,y)= \| x-y \|</math>, falls <math>X</math> und <math>Y</math> Teilmengen eines normierten Vektorraumes sind, oder allgemeiner <math>c(x,y)=h(x-y)</math> für eine differenzierbare Funktion <math>h</math>.

Monge-Problem

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

minimiert.

Es gibt Beispiele, in denen das Monge-Problem keine Lösung besitzt, z. B. falls <math>\mu</math> ein Diracmaß und <math>\nu</math> 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ß <math>\pi</math> auf dem Produktraum <math>X\times Y</math> mit

<math>\pi(A\times Y)=\mu(A), \quad \pi(X\times B)=\nu(B)</math>

für alle kompakten Mengen <math>A\subset X, B\subset Y</math>, welches das Funktional

<math>\int_{X\times Y}c(x,y)d\pi(x,y)</math>

minimiert.

Kantorovich bewies, dass ein solches Wahrscheinlichkeitsmaß immer existiert.

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

<math>\pi=(\operatorname{id}, r)_*\mu</math>

für eine injektive Abbildung <math>r:X\rightarrow Y</math>. Insbesondere hat in diesem Fall auch das Monge-Problem eine Lösung.<ref>Wilfrid Gangbo, Robert J. McCann: The geometry of optimal transportation. In: Acta Mathematica. Bd. 177, Nr. 2, 1996, 113–161, (PDF; 2,8 MB), {{#invoke:Vorlage:Handle|f|scheme=doi|class=plainlinks|parProblem=Problem|errCat=Wikipedia:Vorlagenfehler/Parameter:DOI|errClasses=error editoronly|errHide=1|errNS=0 4 10 100}}.</ref>

Wasserstein-Metriken

{{#if: Wasserstein-Metrik|{{#ifexist:Wasserstein-Metrik|

|{{#if: |{{#ifexist:{{{2}}}|

→ Haupt{{#if:|seite|artikel}}: [[{{{2}}}{{#if: ||{{{titel2}}}}}]]{{#if: |{{#ifexist:{{{3}}}| und [[{{{3}}}{{#if: ||{{{titel3}}}}}]]|}}|}}

|{{#if: |{{#ifexist:{{{3}}}|

→ Haupt{{#if:|seite|artikel}}: [[{{{3}}}{{#if: ||{{{titel3}}}}}]]

|}}|}}|}}|}}|}}|Einbindungsfehler: Die Vorlage Hauptartikel benötigt immer mindestens ein Argument.}}

Für <math>p\ge 1</math> und Wahrscheinlichkeitsmaße <math>\mu,\nu</math> auf einem metrischen Raum X sei <math>\Gamma(\mu,\nu)</math> die Menge aller Wahrscheinlichkeitsmaße auf <math>X\times X</math> mit <math>\pi(A\times X)=\mu(A), \pi(X\times B)=\nu(B)</math> für alle kompakten Mengen <math>A,B \subset X</math>. Dann definiert

<math>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}</math>

den p-ten Wasserstein-Abstand zwischen <math>\mu</math> und <math>\nu</math>.

Der p-te Wasserstein-Abstand <math>W_p</math> definiert eine Metrik auf der Menge aller Wahrscheinlichkeitsmaße auf <math>X</math>, deren p-tes Moment endlich ist.

Wenn <math>X</math> eine konvexe Teilmenge des <math>\R^n</math> und <math>p>1</math> ist, dann sind die Geodäten der p-ten Wasserstein-Metrik von der Form

<math>t \mapsto (F_t)_*\pi</math>,

wobei <math>F_t:X\times X\rightarrow X</math> die durch <math>F_t(x,y)=tx+(1-t)y</math> definierte Abbildung und <math>\pi</math> die Lösung des Kantorovich-Problems zu <math>c(x,y)=d(x,y)^p</math> 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 <math>\mu,\nu</math> 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