Kantorovich Problem

The Kantorovich's optimal transportation problem is one of the basic minimization problems in the field of Optimal Transport. It is named after Leonid Kantorovich who studied various minimization problems and was awarded a Nobel Prize in Economic Sciences in 1975 due to this work.

Introduction

The Kantorovich problem is one of the two basic problems in Optimal Transport, beside Monge Problem (add reference).

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

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

Theorem

Let $\mu \in {\mathcal {P}}(X),\nu \in {\mathcal {P}}(Y)$ where $X,Y$ are Polish spaces. Let $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: $\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) $\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 $\mu$ -almost every $x\in X$ and $\nu$ -almost every $y\in Y$.

Then, $\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>