Kantorovich Problem

The Kantorovich problem is one of the basic minimization problems in Optimal Transport. It is named after Russian mathematician Leonid Kantorovich (reference).

Introduction

There are two basic problems in optimal transport: the Monge problem and the Kantorovich problem. In contrast to the Monge problem, The Kantorovich problem allows a non-empty minimization set, a convex constraint set, and a convex effort functional. 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>