Kantorovich Problem

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 $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 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 \phi(y)} such that the sum of $\phi (x)$ and $\phi (y)$ is always less than the cost $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 $\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 $\pi \in \Pi (\mu ,\nu )$

Kantorovich Duality Statement

Definition

Kantorovich'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:

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 $\pi \in \Pi (\mu ,\nu )$

Theorem

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 \mu \in \mathcal{P}(X), \nu \in \mathcal{P}(Y)} where 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, Y} are Polish spaces. Let $c:X\times Y\rightarrow [0,+\infty ]$ be a lower semi-continuous cost function.

Define 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}} as in the following:

Kantorovich's Optimal Transport Problem

given $\mu \in {\mathcal {P}}(X)$ and 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 \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 )$

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 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 \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>