Kantorovich Problem

The Kantorovich's optimal transportation problem is one of the basic problems in the field of Optimal Transport.

Introduction

The Kantrovich problem admits a dual because it is a linear minimization problem with convex constraints.

Shipping problem

Suppose there is a merchant who is attempting to ship their items from one place to another. They can hire trucks at some cost Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c(x, y)} for each unit of merchandise which is shipped from point Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x} to point $y$. Now the shipper is approached by a mathematician, who claims that prices can be set such that they align with the shipper's financial interests. This would be achieved by setting the price $\phi (x)$ and $\phi (y)$ such that the sum of $\phi (x)$ and $\phi (y)$ is always less than the cost Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c(x, y)} . This may even involve setting negative prices in certain cases. However, it can be shown that the shipper will spend almost as much as they would have if they had opted for the original pricing method.

Kantrovich's Optimal Transport Problem

Given Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu \in \mathcal{P}(X)} and $\nu \in {\mathcal {P}}(Y)$

Minimize:

$\mathbb {K} (\pi )=\int _{X\times Y}c(x,y)\mathrm {d} \pi (x,y)$ over $\pi \in \Pi (\mu ,\nu )$

Kantorovich Duality Statement

Definition

Kantorovich's Optimal Transport Problem: given $\mu \in {\mathcal {P}}(X)$ and $\nu \in {\mathcal {P}}(Y)$

Minimize:

$\mathbb {K} (\pi )=\int _{X\times Y}c(x,y)\mathrm {d} \pi (x,y)$

over Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi \in \Pi(\mu, \nu)}

Theorem

Let $\mu \in {\mathcal {P}}(X),\nu \in {\mathcal {P}}(Y)$ where $X,Y$ are Polish spaces. Let Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c: X \times Y \rightarrow[0,+\infty]} be a lower semi-continuous cost function.

Kantorovich's Optimal Transport Problem

Define $\mathbb {K}$ as in the following:

given $\mu \in {\mathcal {P}}(X)$ and $\nu \in {\mathcal {P}}(Y)$

Minimize: Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mathbb{K}(\pi)=\int_{X \times Y} c(x, y) \mathrm{d} \pi(x, y) } over Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \pi \in \Pi(\mu, \nu)}

and $\mathbb {J}$ by (need reference 3.1) Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \quad \mathbb{J}: L^{1}(\mu) \times L^{1}(\nu) \rightarrow \mathbb{R}, \quad \mathbb{J}(\varphi, \psi)=\int_{X} \varphi \mathrm{d} \mu+\int_{Y} \psi \mathrm{d} \nu }

Let $\Phi _{c}$ be defined by $\Phi _{c}=\left\{(\varphi ,\psi )\in L^{1}(\mu )\times L^{1}(\nu ):\varphi (x)+\psi (y)\leq c(x,y)\right\}$ where the inequality is understood to hold for Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \mu} -almost every $x\in X$ and $\nu$ -almost every $y\in Y$.

Then, Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \min _{\pi \in \Pi(\mu, \nu)} \mathbb{K}(\pi)=\sup _{(\varphi, \psi) \in \Phi_{c}} \mathbb{J}(\varphi, \psi) }

References:

An article on Kantorovich problem References Villani (1-3, 6-9), Santambrogio (xv-xvii,1-9)

References

</ references>