Kantorovich Problem

The Kantorovich problem is one of the basic minimization problems in optimal transport. It is named after Russian mathematician and Nobel Laureate Leonid Kantorovich.

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.

Kantorovich Optimal Transport Problem

Consider the basic premises of optimal mass transportation. Consider probability spaces $(X,\mu )$ and $(Y,\nu )$. Let $c$ be a nonnegative measurable function on $X\times Y$. The Kantorovich problem is the following:

$\pi \longmapsto \int _{X\times Y}c(x,y)d\pi (x,y)(1)$

This is on the convex set $\Pi (\mu ,\nu )$ which is also nonempty. Note $\pi \in \Pi (\mu ,\nu )$ if and only if $\pi$ is a nonnegative measure which satisfies:

$\pi [A\times Y]=\mu [A],\quad \pi [X\times B]=\nu [B]$

for all measurable subsets $A$ of $X$ and $B$ of $Y$. This definition implies that $\pi$ is a probability measure. Another way to say this is that $\pi \in \Pi (\mu ,\nu )$ if and only if it is a nonnegative measure on $X\times Y$ such that, for all measurable functions $(\varphi ,\psi )\in L^{1}(d\mu )\times L^{1}(d\nu ),$ or equivalently $L^{\infty }(d\mu )\times L^{\infty }(d\nu )$

$\int _{X\times Y}[\varphi (x)+\psi (y)]d\pi (x,y)=\int _{X}\varphi d\mu +\int _{Y}\psi d\nu$ (2)

Remarks

There are some topological assumptions that can be made on the measure spaces $(X,\mu )$ and $(Y,\nu )$. When $X$ and $Y$ are Polish spaces (i.e. completely metrizable and separable spaces), and $\mu ,\nu$ are Borel probability measures, it is sufficient to impose the expression above for $(\varphi ,\psi )\in C_{b}(X)\times C_{b}(Y)$ only .

In addition if $X$ and $Y$ are locally compact. then one can even be content with imposing (2) for $(\varphi ,\psi )\in C_{0}(X)\times C_{0}(Y)$. Note that $C_{b}(X)$ is the space of bounded continuous functions on $X,$ and $C_{0}(X)$ the space of continuous functions going to 0 at infinity, i.e. those continuous functions $\varphi$ such that for any $\varepsilon >0$ there is a compact set $K_{\varepsilon }\subset X$ satisfying $\sup _{x\notin K_{e}}|\varphi (x)|\leq \varepsilon ;$ note that$C_{0}(X)\subset C_{b}(X).$ This possibility to restrict the class of test functions to the narrower space $C_{0}$ when $X$ and $Y$ are locally compact is due to Riesz' theorem, which identifies the space $M(X)$ of Borel measures having finite total variation on $X$ with the topological dual of $C_{0}(X)$.

Kantorovich Duality

Since the Kantorovich problem is a linear minimization problem with convex constraints it admits a dual. Kantorovich expressed this in 1942, where he considered the case in which the cost function may be conceived of as a distance: function is a distance: $c(x,y)=d(x,y)$.

Theorem

Let $X$ and $Y$ be Polish spaces, let $\mu \in P(X)$ and $\nu \in P(Y),$ and let $c:X\times Y\rightarrow \mathbb {R} _{+}\cup \{+\infty \}$ be a lower semi-continuous cost function.

Whenever $\pi \in P(X\times Y)$ and $(\varphi ,\psi )\in L^{1}(d\mu )\times L^{1}(d\nu ),$ define

$I[\pi ]=\int _{X\times Y}c(x,y)d\pi (x,y),\quad J(\varphi ,\psi )=\int _{X}\varphi d\mu +\int _{Y}\psi d\nu$

Define $\Pi (\mu ,\nu )$ to be the set of all Borel probability measures $\pi$ on $X\times Y$ such that for all measurable subsets $A\subset X$ and $B\subset Y$.

$\pi [A\times Y]=\mu [A],\quad \pi [X\times B]=\nu [B]$

and define $\Phi _{c}$ to be the set of all measurable functions $(\varphi ,\psi )\in L^{1}(d\mu )\times$ $L^{1}(d\nu )$ satisfying

$\varphi (x)+\psi (y)\leq c(x,y)$

for d $\mu$-almost all $x\in X,d\nu$ -almost all $y\in Y$ ( $\forall (x,y)$ outside of $(\mu \otimes \nu )$ negligible set.

Then

$\inf _{\Pi (\mu ,\nu )}I[\pi ]=\sup _{\Phi _{e}}J(\varphi ,\psi )$

If the definition of $\Phi _{c}$ to those functions $(\varphi ,\psi )$ that are continuous and bounded, then the supremum on the right hand side of (3) is not affected.