Monge formulation

A (strict) formulation of the optimal transport problem. It’s always taught with dirt piles; why deviate from tradition.

Consider dirt piles at locations $D_1,\dots ,D_n$ and holes at locations $H_1,\dots ,H_m$. Suppose pile $D_i$ has ${\alpha }_i$ units of dirt and hole $H_j$ can hold ${\beta }_j$ units of dirt. It costs $c(i,j)\ge 0$ to transport a unit of dirt from $D_i$ to $H_j$. Our question is: Which dirt pile do we send to which hole in order to minimize the overall cost?

More formally, we want a transportation plan $T:[n]\to [m]$ which maps piles to holes, telling us where to send the $i$-th dirt pile. Each pile can only be sent to one hole, and at the end of the process, each hole should be full. That is, for each $j$, we should have ${\sum }_i{\alpha }_i{\delta }_{T(i)=j}={\beta }_j$.

We are thus looking to solve the following problem:

$$\underset{T}{\min }\{\sum _i{\alpha }_{i}c(i,T(i))|\sum _i{\alpha }_i{\delta }_{T(i)=j}={\beta }_j,\forall j\in [m]\}.$$

This is the Monge formulation in the discrete case.

To see what this has to do with probability, suppose that $D_1,\dots ,D_n$ and $H_1,\dots ,H_m$ represent two discrete distributions, with mass ${\alpha }_i$ at $D_i$ and mass ${\beta }_j$ at $H_j$. That is, ${\alpha }_1,\dots ,{\alpha }_n$ and ${\beta }_1,\dots ,{\beta }_m$ constitute two discrete probability measures $\alpha ={\mathbb{P}}_{\alpha }$ and $\beta ={\mathbb{P}}_{\beta }$. $T$ is a map between these two measures that obeys

$${\beta }_j={\mathbb{P}}_{\beta }(j)={\mathbb{P}}_{\alpha }(T^{-1}(j))={\mathbb{P}}_{\alpha }(\{i:T(i)=j\}).$$

That is, the pushforward measure ${\alpha }_{\ast }(T)$ must be equivalent to the distribution $\beta$. With this perspective in mind, we can also notice that ${\sum }_i{\alpha }_{i}c(i,T(i))$ is simply the expected value of $c(X,t(X))$ when $X\sim \alpha$. This motivates the extension of the discrete Monge formulation to the continuous case:

$$\underset{T}{\inf }\{{\mathbb{E}}_{X\sim \alpha }c(X,T(X))|{\alpha }_{\ast }(T)=\beta \}.$$

This is the (continuous) Monge formulation, and a map $T$ solving the above problem is sometimes called a Monge map (or a transportation plan). There’s an obvious problem with this formulation, however: What if there is no mapping between piles and holes such that each hole will be filled by each pile. That is, what if there is no map $T$ such that ${\alpha }_{\ast }(T)=\beta$. In fact, this is a very restrictive requirement in many applications. This is what motivates the Kantorovich relaxation and optimal transport costs.