Kantorovich Problem

The Kantorovich problem is one of the two essential minimization problems in optimal transport (the other being the Monge problem). It is named after Russian mathematician and Nobel Laureate Leonid Kantorovich.

Kantorovich Problem. The Kantorovich Problem (like the Monge Problem) can be visualized as distributing piles of sand into holes (of equal volume) in an optimal fashion.

Introduction

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

The intuition behind the Kantorovich problem can be given by an explanation of optimizing shipments. Suppose there is a merchant who is attempting to ship items from one place to another. She 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 she would have if she had opted for the original pricing method .

Kantorovich Optimal Transport Problem

Transport Plans

The Monge problem was about the optimal way to rearrange mass . Note that in the Monge formulation of the optimal transport problem, the mass cannot be split and thus it is mapped $x\mapsto T(x)$. When considering discrete cases, this results in problems when trying to establish maps T such that $T_{\#}\mu =\nu$. Kantorovich made the observation that the mass in question could be split, which makes the problem much easier to model . Allowing the mass to be split results in a relaxation of the problem (e.g. half of the mass from $x_{1}$ can go to $y_{1}$ and half can go to $y_{2}$, and so on). To model this consider $d\pi (x,y)$, which denotes the mass transported from x to y. This allows the mass to be moved to multiple places. Also consider $\mu (A)$ and $\nu (B)$: where the total mass taken from measurable set $A\in X$ must be equal to $\mu (A)$ and the total mass taken from measurable set $B\in Y$ must equal $\nu (B)$.

The constraints of the problem can be written in the following manner:

$\pi (A\times Y)=\mu (A)$

$\quad \pi (X\times B)=\nu (B)\quad$

for all measurable sets $A\subseteq X,B\subseteq Y$

If we have a $\pi$ that satisfies these constraints, the set of such $\pi$ is referred to as $\Pi (\mu ,\nu )$. This is the set of transport plans between $\mu$ and $\nu$. Notice again that now we are dealing with transport plans instead of the transport maps that are used in the Monge formulation of the problem .

Problem Statement

Given $\mu \in {\mathcal {P}}(X)$ and $\nu \in {\mathcal {P}}(Y)$, solve

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

over $\pi \in \Pi (\mu ,\nu )$

Assuming there is a transport map $T^{\dagger }:X\rightarrow Y$ for the Monge problem, we define $\mathrm {d} \pi (x,y)=\mathrm {d} \mu (x)\delta _{y=T^{\dagger }(x)}$. Using this we can see that:

${\begin{aligned}\pi (A\times Y)&=\int _{A}\delta _{T^{\dagger }(x)\in Y}\mathrm {d} \mu (x)=\mu (A)\\\pi (X\times B)&=\int _{X}\delta _{T^{\dagger }(x)\in B}\mathrm {d} \mu (x)=T_{\#}^{\dagger }\mu (B)=\nu (B)\end{aligned}}$

We can see that $\int _{X\times Y}c(x,y)\mathrm {d} \pi (x,y)=\int _{X}c\left(x,T^{\dagger }(x)\right)\mathrm {d} \mu (x)$

thus $\inf \mathbb {K} (\pi )\leq \inf \mathbb {M} (T)$.

Kantorovich Duality

Since the Kantorovich problem is a linear minimization problem with convex constraints it admits a dual problem. The astute reader may notice that this is a linear programming problem--Kantorovich is also considered to be the founder of linear programming.