Monge Problem

The optimal transport problem first came up in the 18th century, brought by Gaspard Monge. The original problem is called the Monge Problem, which wants to find an optimal way to rearrange the dirt dig out from the land into castle walls or other desired shapes. The "optimal way" means the way with the minimal "cost", or workload. In the following, we will first formulate the Monge problem, then explain why it is a challenging problem. On top of that, we introduce the Kantorovich's problem which is a generalized version of Monge problem but it perfectly tackles the challenges. Finally, we introduce Brenier's theorem and discuss the solvability of these two problems.

Formulation of Monge Problem

To begin with, we use probability measures to represent the piles of dirt. Suppose $(X,d)$ is a metric space that is equipped with a natural topology generated by all the open balls. The topology defines the collection of open sets, and we denote ${\mathcal {B}}(X)$ as the $\sigma$-algebra generated by the open sets, which is called the Borel $\sigma$-algebra on the metric space $(X,d)$. Denote ${\mathcal {M}}(X)$ as the set of all finite measures(a pile has finite amount of dirt!) defined on the measurable space $(X,{\mathcal {B}}(X))$. For a measure $\mu \in {\mathcal {M}}(X)$ and $B\in {\mathcal {B}}(X)$, $\mu (B)$ represents how much dirt is contained in the set $B$, so a measure can precisely characterize the shape of a dirt pile. When we rearrange the dirt pile, we keep the total amount unchanged, so without losing of generality we can assume the total mass $\mu (X)=1$, meaning we restrict our attention to the set of all probability measures on $(X,{\mathcal {B}}(X))$, denoted by ${\mathcal {P}}(X)$.

The next step is to define the behavior of "transport". A possible way is to use the following notion of transport map.

Definition 1. Transport map

Give two probability measures $\mu ,\nu \in {\mathcal {P}}(X)$, a measurable function $t:X\rightarrow X$ transports $\mu$ onto $\nu$ if

$\nu (B)=\mu (t^{-1}(B)),\ \forall \ B\in {\mathcal {B}}(X)$

where $t^{-1}=\{x\in X:t(x)\in B\}$ is the preimage. We call $\nu$ the push-forward measure of $\mu$ under $t$, denoted by $\nu =t_{\#}\mu$ or $\nu =\mu \circ t^{-1}$.

The intuition of this definition is that a transport map $t$ moves all of the dirt at $x\in X$ to the location $t(x)$. Now we can formulate the Monge problem mathematically.

Definition 2. Monge's Problem

Given $\mu ,\nu \in {\mathcal {P}}(X)$, Monge problem is the following optimization problem.

$\inf _{t}\int _{X}|t(x)-x|d\mu (x),\ s.t.\ t:X\rightarrow X\ {\text{is measurable and }}t_{\#}\mu =\nu$

To illustrate, $|t(x)-x|$ is the distance of moving the dirt from $x$ to $t(x)$, and the integral $\int _{X}|t(x)-x|d\mu (x)$ is the total cost or effort. The condition $t_{\#}\mu =\nu$ ensures that $t$ is a transport map from $\mu$ onto $\nu$, meaning $t$ rearranges the dirt in the shape of $\mu$ to look like that of $\nu$. If $t$ solves the Monge problem, meaning it realized the infimum, then we call it an optimal transport map. Here, we use the cost function $c(x^{1},x^{2})=|x^{1}-x^{2}|$, but it can also be replaced by other general cost functions. The problem can easily be generalized to the one regarding two different spaces $X,Y$, with $\mu \in {\mathcal {P}}(X)$, $\nu \in {\mathcal {P}}(Y)$ and $c:X\times Y\rightarrow [0,\infty )$ is the cost function, but it is essentially the same as the one regarding the same space.

The Monge problem is important because it provides us with spatial insight of how far two probability measures are. If two probability measures are "closed to each other", there should be some transport map such that the total effort of transport is small. This idea leads to the concept of Wasserstein metric.

Challenges of Monge Problem

The Monge problem turns out to be a very challenging problem for several reasons as follows.

• The constraint set can be empty. Given $\mu ,\nu \in {\mathcal {P}}(X)$, it does not necessarily exist a transport map from $\mu$ onto $\nu$: $t_{\#}\mu =\nu$. For example, consider $\mu =\delta _{0}$, the point mass at $0$, and $\nu$ is the uniform measure on $[0,1]$. For every measurable function $t:X\rightarrow X$, $t_{\#}\mu$ should be a point mass at $t(0)$ so $t$ cannot yield a uniform distribution on $[0,1]$. The reason is that a transport map cannot split the mass concentrated at one point$---$it transports all the mass at point $x$ to the location $t(x)$.

• Solutions may not be unique. Let $\mu$, $\nu$ be the uniform distribution on $(0,1)$ and $(1/4,5/4)$ respectively. Consider the following two transport maps.

(1) Transport all the mass on $(0,1/4)$ to $(1,5/4)$ and keep the rest unchanged. In this case,

$t_{0}(x)={\begin{cases}x+1,&x\in (0,1/4);\\x,&x\in (1/4,1);\end{cases}}$

is the transport map and the cost is $\int |t_{0}(x)-x|d\mu (x)=\int _{0}^{1/4}1dx=1/4$.

(2) Shift all the mass to the right by $1/4$. In this case, $t_{1}(x)=x+1/4$ is the transport map and the cost is $\int |t_{1}(x)-x|d\mu (x)=\int _{0}^{1}1/4dx=1/4$.

It is not hard to imagine that other methods of transport will cause larger effort, so this problem has two different optimal solutions.

• The constraint set is not convex. In general, for an optimization problem, we usually take an initial guess of the solution and perturb it to see if the objective function decreases. The convexity of constraint set guarantees that the point after perturbation is still in the constraint set. However, this is not always true for Monge problem. Consider the transport maps $t_{0}$ and $t_{1}$ defined in the last example. Their convex combination is

$t_{\alpha }(x)=(1-\alpha )t_{0}(x)+\alpha t_{1}(x)={\begin{cases}(1-\alpha )(x+1/4)+\alpha (x+1),&x\in (0,1/4);\\(1-\alpha )(x+1/4)+\alpha x,&x\in (1/4,1);\end{cases}}$

Take $\alpha =1/2$, we have

$t_{1/2}(x){\begin{cases}x+5/8,&x\in (0,1/4);\\x+1/8,&x\in (1/4,1);\end{cases}}$

Then $\nu ((5/8,3/4))=1/8$, but $(t_{{1/2}\#}\mu )((5/8,3/4))=\mu ((0,1/8)\cup (1/2,5/8))=1/4$, so $t_{1/2}$ does not give a transport map from $\mu$ onto $\nu$ any more.

A generalized problem: Kantorovich's Problem

An approach to tackle the problems mentioned in Section II is to use a "transport plan" instead of a transport map. This gives a more generalized version of the problem called Kantorovich Problem.

Definition 3. Transport plan

Given $\mu ,\nu \in {\mathcal {P}}(X)$, a transport plan is a probability measure $\gamma \in {\mathcal {P}}(X\times X)$ on the product space $(X\times X,{\mathcal {B}}(X\times X))$ such that $(\pi ^{1})_{\#}\gamma =\mu$, $(\pi ^{2})_{\#}\gamma =\nu$, where $\pi ^{i}:X\times X\rightarrow X$, $\pi ^{i}(x_{1},x_{2})=x_{i}$, $i=1,2$ are projection maps. The set of all transport plans from $\mu$ to $\nu$ is denoted by $\Gamma (\mu ,\nu )$.

The conditions $(\pi ^{1})_{\#}\gamma =\mu$, $(\pi ^{2})_{\#}\gamma =\nu$ give the right marginals:

$\mu (A)=((\pi ^{1})_{\#}\gamma )(A)=\gamma ((\pi ^{1})^{-1}(A))=\gamma (A\times X),\ \nu (B)=((\pi ^{2})_{\#}\gamma )(A)=\gamma ((\pi ^{2})^{-1}(A))=\gamma (X\times B)$

Therefore, a transport plan is a probability measure on the product space $X\times X$ that has marginals distributions $\mu$ and $\nu$. In addition, $\gamma (A\times B)$ represents the amount of mass taken from set $A$ that is sent to set $B$. Since $\gamma (A\times B)\leq \gamma (A\times X)=\mu (A)$, a transport plan can move only a fraction but not necessarily all of the mass at some place to other locations, and this solves the problem that a transport map cannot split a point mass. Moreover, any transport map can be represented as a transport plan: if $t$ is a transport map with $t_{\#}\mu =\nu$, then $\gamma \equiv (id\times t)_{\#}\mu$ is a transport plan in $\Gamma (\mu ,\nu )$, where $id$ is the identity map.

Based on the notion of transport plans, we can state Kantorovich's problem, which is a problem more general than Monge problem. Instead of optimizing the cost over all transport maps, it minimizes the cost over all transport plans.

Definition 4. Kantorovich's problem

Given $\mu ,\nu \in {\mathcal {P}}(X)$, the following optimization problem is the Kantorovich's problem:

$\inf _{\gamma :\gamma \in \Gamma (\mu ,\nu )}\int _{X\times X}|x^{1}-x^{2}|^{p}d\gamma (x^{1},x^{2}),\ p\geq 1$

Denote the cost by $\mathbb {K} _{p}(\gamma )\equiv \int _{X\times X}|x^{1}-x^{2}|d\gamma (x^{1},x^{2})$, which is a functional on $\Gamma (\mu ,\nu )$. If $\gamma$ attains the infimum, we call it an optimal transport plan. Here, we use the cost function $c(x^{1},x^{2})=|x^{1}-x^{2}|^{p}$, but it can also be replaced by other general cost functions.

The Kantorovich's problem is a better-behaved problem for the following reasons.

• The constraint sets is always nonempty. For $\mu ,\nu \in {\mathcal {P}}(X)$, the product measure $\mu \times \nu$ is always a transport plan in $\Gamma (\mu ,\nu )$.
• The constraint set is convex. Take $\gamma _{0}$, $\gamma _{1}\in \Gamma (\mu ,\nu )$, the convex combination is $\gamma _{\alpha }\equiv (1-\alpha )\gamma _{0}+\alpha \gamma _{1},\ \alpha \in [0,1]$. Notice that it gives the right marginals: $(\pi _{\#}^{1}\gamma _{\alpha })(A)=\gamma _{\alpha }(A\times X)=(1-\alpha )\gamma _{0}(A\times X)+\alpha \gamma _{1}(A\times X)=(1-\alpha )\mu (A)+\alpha \mu (A)=\mu (A)$, and $(\pi _{\#}^{2}\gamma _{\alpha })(B)=\nu (B)$ holds similarly.

• The objective function is convex as well. Notice that $\mathbb {K} _{p}(\gamma _{\alpha })=(1-\alpha )\mathbb {K} _{p}(\gamma _{0})+\alpha \mathbb {K} _{p}(\gamma _{1})$, so objective function is actually linear.
• Kantorovich's problem has a dual problem.
• The minimizer exists via the direct method of the calculus of variations.

Brenier's Theorem, Solvability of the problem

In this section, we consider a special case where $X=\mathbb {R} ^{d}$ and the cost function is quadratic: $c(x^{1},x^{2})=|x^{1}-x^{2}|^{2}$. These assumptions allow us to obtain quite strong results for the solvability of Monge and Kantorovich's problems, which is known as the following Brenier's theorem.

Theorem 1. Brenier's theorem

Given $\mu ,\nu \in {\mathcal {P}}_{2}(\mathbb {R} ^{d})$, $\mu \ll {\mathcal {L}}^{d}$, where ${\mathcal {P}}_{2}(\mathbb {R} ^{d})\equiv \{\mu \in {\mathcal {P}}(\mathbb {R} ^{d}):\int |x|^{2}d\mu (x)<\infty \}$ and ${\mathcal {L}}^{d}$ is the Lebesgue measure on $\mathbb {R} ^{d}$. Then there exists a unique optimal transport plan $\gamma _{\star }$ of the form $\gamma _{\star }=(id\times t_{\star })_{\#}\mu$ for the Kantorovich's problem, where $t_{\star }:\mathbb {R} ^{d}\rightarrow \mathbb {R} ^{d}$ is a measurable function. Notice that $t_{\star }$ is actually a transport map from $\mu$ onto $\nu$, so $t_{\star }$ solves the corresponding Monge problem. In particular, the optimal cost of two problems coincide:

$\inf _{t:t_{\#}\mu =\nu }\mathbb {M} _{2}(t)=\inf _{\gamma \in \Gamma (\mu ,\nu )}\mathbb {K} _{2}(\gamma )$

where $\mathbb {M} _{2}(t)\equiv \int |t(x)-x|^{2}d\mu (x)$.

The proof of the result relies heavily on the duality property of the Kantorovich's problem. By passing to the dual problem, we are able to give the expression of $t$ as the gradient of the Kantorovich potential. The assumption that $\mu$ is absolute continuous w.r.t Lebesgue measure can be weakened to not giving mass on sets of $d-1$ dimensional Hausdorff measure , and the result still holds for cost functions in the form of $c(x^{1},x^{2})=h(x^{1}-x^{2})$ for some convex function $h$.