Problems of Monge and Kantorovich

In this article, we will talk about the problems of Monge and Kantorovich and the corresponding existence of solutions.

Monge Problem

Problem 1.1 (Monge Problem). Given $\mu \in \mathcal{P}(X)$, $\nu \in \mathcal{P}(Y)$ and a Borel measurable cost function
$$
c:X \times Y \to [0,+\infty],
$$
solve
$$
(\mathrm{MP}) \qquad \inf \left\{ M(T):=\int_X c(x,T(x))\ d\mu(x) \ \middle|\ T_\sharp\mu=\nu \right\},
$$
where
$$
T_\sharp\mu(A)=\mu\bigl(T^{-1}(A)\bigr)
$$
for all $A \in \mathcal{B}(Y)$. Find also the optimal transport map $T$.

Remark. Difficulty of Monge Problem is that the constraint
$$
\{T:X \to Y \mid T_\sharp\mu=\nu\}
$$
is often not closed under weak convergence.

Example. $X=[0,2\pi]$, $\mu=\dfrac{1}{2\pi}\ dx$, $T_n(x)=\sin(nx)$, $Y=\mathbb R$.

Claim. For all $n \in \mathbb{N}$,

$$
(T_n)_\sharp\mu=\nu,
$$

where

$$
\nu(dy)=\frac{1}{\pi\sqrt{1-y^2}}\ 1_{(-1,1)}(y)\ dy.
$$

Proof : For all $\varphi \in C_b(\mathbb R)$,

$$
\begin{aligned}
\int_Y \varphi(y)\ ((T_n)_\sharp\mu)(dy)
&=
\int_X \varphi(\sin nx)\ \mu(dx)
=
\frac{1}{2\pi}\int_0^{2\pi}\varphi(\sin nx)\ dx \\\
&=\frac{1}{2\pi n} \int_0^{2\pi n}\varphi(\sin u)\ du
=\frac{1}{2\pi}\int_0^{2\pi}\varphi(\sin u)\ du
=\int_Y \varphi(y)\ \nu(dy).
\end{aligned}
$$

Hence $(T_n)_\sharp\mu=\nu$ for all $n \in \mathbb{N}$.

However, by Riemann-Lebesgue Lemma, in $L^p[0,2\pi]$, $1 \leq p < +\infty$, we have for all $g \in L^q[0,2\pi]$
$$
\int_0^{2\pi} g(x)\sin(nx)\ dx \to 0.
$$
Hence
$$
T_n \rightharpoonup 0.
$$
But for $T=0$, $T_\sharp\mu=\delta_0 \neq \nu$, which shows that
$$
\left\{ T \in L^p([0,2\pi]) \ ; \ T_\sharp\mu=\nu \right\}
$$
is not closed under weak topology of $L^p[0,2\pi]$.

Kantorovich Problem

Problem 1.2 (Kantorovich Problem). Given $\mu \in \mathcal{P}(X)$, $\nu \in \mathcal{P}(Y)$, and a Borel measurable cost function
$$
c:X \times Y \to [0,\infty],
$$
find
$$
(\mathrm{KP}) \qquad \inf \left\{ K(\gamma):=\int_{X \times Y} c\ d\gamma \ \middle|\ \gamma \in \Pi(\mu,\nu) \right\},
$$
where $\Pi(\mu,\nu)$ is the set of so-called transport plans, i.e.
$$
\Pi(\mu,\nu)
=
\left\{
\gamma \in \mathcal{P}(X \times Y)
\ \middle|\
(\pi_x)_\sharp\gamma=\mu,\ (\pi_y)_\sharp\gamma=\nu
\right\},
$$
where $\pi_x$ and $\pi_y$ are two projections of $X \times Y$ onto $X$ and $Y$, respectively.

Remark. If $T_\sharp\mu=\nu$ then the plan
$$
\pi=(\mathrm{id} \times T)_\sharp\mu \in \Pi(\mu,\nu).
$$
Conversely, if $\pi=(\mathrm{id} \times T)_\sharp\mu \in \Pi(\mu,\nu)$, then $T_\sharp\mu=\nu$.

Proof : First, if $T_\sharp\mu=\nu$, then for all $A \in \mathcal{B}(X)$, $B \in \mathcal{B}(Y)$,
$$
\pi(A \times Y)
=
((\mathrm{id} \times T)_\sharp\mu)(A \times Y)
=
\mu\bigl((\mathrm{id} \times T)^{-1}(A \times Y)\bigr)
=
\mu(A),
$$
and
$$
\pi(X \times B)
=
((\mathrm{id} \times T)_\sharp\mu)(X \times B)
=
\mu\bigl((\mathrm{id} \times T)^{-1}(X \times B)\bigr)
=
\mu(T^{-1}(B))
=
\nu(B).
$$
Hence $\pi \in \Pi(\mu,\nu)$.

Second, if $\pi \in \Pi(\mu,\nu)$, then for all $B \in \mathcal{B}(Y)$,
$$
\nu(B)
=
\pi(X \times B)
=
((\mathrm{id} \times T)_\sharp\mu)(X \times B)
=
\mu\bigl((\mathrm{id} \times T)^{-1}(X \times B)\bigr)
=
\mu(T^{-1}(B)).
$$
Hence $T_\sharp\mu=\nu$. $\square$

Remark. In the problem of Monge, it may happen that there is no map $T$ such that $T_\sharp\mu=\nu$. Indeed, if $\mu=\delta_{x_0}$, $x_0 \in X$ and $\nu$ is any measure that is different from an atomic measure on one atom, then there is no such map, as
$$
T_\sharp\mu=\delta_{T(x_0)}.
$$
But the set $\Pi(\mu,\nu)$ is always non-empty, as
$$
\mu \otimes \nu \in \Pi(\mu,\nu).
$$

Weak-$\star$ Convergence and Weak Convergence

Let $\mathcal{M}(X)$ be the set of finite signed measures on $X$. By Riesz Representation theorem, if $X$ is separable and locally compact metric space, let $\mathcal{X}=C_0(X)$ be the set of continuous functions on $X$ vanishing at infinity, i.e. $f \in C_0(X)$ if and only if $f \in C_b(X)$ and for every $\varepsilon>0$, there exists a compact subset $K \subset X$ such that
$$
|f(x)|<\varepsilon
$$
on $X \setminus K$.

And endow this space with sup norm. Since $C_0(X) \subset C_b(X)$, then $C_0(X)$ is a closed subset of $C_b(X)$ also a Banach space. By Riesz Representation Theorem for all $\xi \in \mathcal{X}’$, there exists a unique $\lambda \in \mathcal{M}(X)$ such that
$$
\langle \xi,\varphi\rangle=\int_X \varphi\ d\lambda
$$
for every $\varphi \in \mathcal{X}=C_0(X)$.

Moreover $\mathcal{X}^\prime \simeq \mathcal{M}(X)$ endowed with the norm $\Vert\lambda\Vert:=|\lambda|(X).$

For signed measures $\mathcal{M}(X)$:

• weak-$\star$ convergence: the convergence in the duality with $C_0(X)$, that is $\mu_n \overset{\mathrm{weak}-\star}{\longrightarrow} \mu$ if and only if for all $\varphi \in C_0(X)$

$$
\int_X \varphi\ d\mu_n \to \int_X \varphi\ d\mu
\qquad \text{as } n \to \infty.
$$

• weak convergence (also called narrow convergence): $\mu_n \rightharpoonup \mu$ if and only if for all $\varphi \in C_b(X)$

$$
\int_X \varphi\ d\mu_n \to \int_X \varphi\ d\mu
\qquad \text{as } n \to \infty.
$$

If $X$ is compact, then $C_0(X)=C_b(X)=C(X)$, weak-$\star$ convergence and weak convergence are the same.

Existence of Solutions

Theorem 1.1. Suppose that $X,Y$ are compact and $c:X \times Y \to \mathbb R$ is continuous. Then the Kantorovich Problem admits a minimizer.

Proof : We just need to show that the set $\Pi(\mu,\nu)$ is compact and that
$$
\gamma \longmapsto K(\gamma)=\int_{X \times Y} c\ d\gamma
$$
is continuous. Since $X \times Y$ compact, $C_0(X \times Y)=C_b(X \times Y)=C(X \times Y)$, $\gamma \mapsto K(\gamma)$ is continuous.

For the compactness, take $(\gamma_n) \subset \Pi(\mu,\nu)$, since they are probability measures, they are bounded in $\mathcal{M}(X \times Y) \simeq (C(X \times Y))’$. By Banach-Alaoglu theorem, there exists a subsequence $\gamma_{n_k}$,
$$
\gamma_{n_k} \overset{\mathrm{weak}-\star}{\longrightarrow} \gamma \in \mathcal{M}(X \times Y).
$$
Since $X \times Y$ is compact,
$$
\gamma(X \times Y)
=
\int_{X \times Y} 1\ d\gamma
=
\lim_{k \to \infty}\int_{X \times Y} 1\ d\gamma_{n_k}
=
1.
$$
Hence $\gamma \in \mathcal{P}(X \times Y)$. Moreover, for all $\varphi \in C(X)$, and since $\gamma_{n_k} \in \Pi(\mu,\nu)$,
$$
\int_{X \times Y} \varphi\ d\gamma_{n_k}
=
\int_X \varphi\ d\mu.
$$
Let $k \to \infty$, we have
$$
\int_{X \times Y} \varphi\ d\gamma
=
\int_X \varphi\ d\mu.
$$
Hence $(\pi_x)_\sharp\gamma=\mu$ and similarly, $(\pi_y)_\sharp\gamma=\nu$. Hence $\gamma \in \Pi(\mu,\nu)$. Therefore, $\Pi(\mu,\nu)$ is compact. $\square$

Lemma 1.1. Let $f:X \to \mathbb R \cup \{+\infty\}$ be a function bounded from below. Then $f$ is lower semi-continuous if and only if there exists a sequence $f_k$ of $k$-Lipschitz functions such that for every $x \in X$, $f_k(x)$ converges increasingly to $f(x)$. Furthermore, $f_k$ can also be made bounded.

Proof : On the one hand, if
$$
f(x)=\lim_{k \to \infty} f_k(x)
$$
for all $x \in X$ with $f_k$ $k$-Lipschitz and increasing, then
$$
f=\sup_k f_k
$$
is also lower semi-continuous.

On the other hand, if $f$ is lower semi-continuous and bounded from below, define
$$
f_k(x)=\inf_y \{ f(y)+k\ d(x,y) \}.
$$
It is easy to show that $f_k$ is $k$-Lipschitz. For fixed $x \in X$, $f_k(x)$ is increasing and we have
$$
\inf f \leq f_k(x) \leq f(x).
$$
We just need to show that
$$
\ell:=\lim_{k \to \infty} f_k(x)=\sup_k f_k(x)=f(x).
$$
Suppose by contradiction $\ell<f(x)$, which implies $\ell<+\infty$. For every $k$, choose $y_k$ such that
$$
f(y_k)\leq f(y_k)+k\ d(x,y_k)<f_k(x)+\frac{1}{k}\leq \ell+\frac{1}{k}. \tag{1}
$$
We get
$$
d(y_k,x)\leq \frac{\ell+\frac{1}{k}-f(y_k)}{k}\leq \frac{C}{k}
$$
(since $\ell<\infty$, $f$ bounded from below). Hence $y_k \to x$. Let $k \to \infty$ in $(1)$. Since $f$ is lower semi-continuous,
$$
f(x)\leq \liminf_{k \to \infty} f(y_k)\leq \lim_{k \to \infty} f_k(x)=\ell,
$$
which gives a contradiction.

Finally, $f_k$ can be made bounded by taking $f_k \wedge k$. $\square$

Lemma 1.2. If $f:X \to \mathbb R \cup \{+\infty\}$ is a lower semi-continuous function, bounded from below on a metric space $X$, then the functional
$$
J:\mathcal{M}_+(X)\to \mathbb R\cup\{+\infty\}
$$
defined on positive measures on $X$ through
$$
J(\mu):=\int_X f\ d\mu
$$
is lower semi-continuous for the weak convergence of measures.

Proof : By Lemma 1.1, there exists a sequence $f_k$ of continuous and bounded functions converging increasingly to $f$. Then write
$$
J(\mu)=\sup_k J_k(\mu):=\int_X f_k\ d\mu
$$
(Actually $J_k \leq J$ and $J_k(\mu)\to J(\mu)$ for every $\mu$ by monotone convergence.)

Since every $J_k$ is continuous for the weak convergence, hence $J$ is a lower semi-continuous functional. $\square$

Theorem 1.2. Let $X$ and $Y$ be compact metric spaces, $\mu \in \mathcal{P}(X)$, $\nu \in \mathcal{P}(Y)$ and
$$
c:X \times Y \to \mathbb R\cup\{+\infty\}
$$
be lower semi-continuous and bounded from below. Then the Kantorovich Problem $(\mathrm{KP})$ admits a solution.

Proof : By Lemma 1.2
$$
\gamma \mapsto K(\gamma)=\int_{X \times Y} c\ d\gamma
$$
is lower semi-continuous. By the proof of Theorem 1.1, we know $\Pi(\mu,\nu)$ is compact. $\square$

Theorem 1.3. Let $X$ and $Y$ be Polish spaces, $\mu \in \mathcal{P}(X)$, $\nu \in \mathcal{P}(Y)$ and
$$
c:X \times Y \to \mathbb R\cup\{+\infty\}
$$
is lower semi-continuous. Then $(\mathrm{KP})$ admits a solution.

Proof : We only need to prove the compactness of $\Pi(\mu,\nu)$.

Since $\mu$ and $\nu$ are finite Borel measures on Polish spaces, by Ulam theorem, $\mu$ and $\nu$ are tight, there exist $K_X \subset X$ and $K_Y \subset Y$ such that
$$
\mu(X \setminus K_X)<\frac{\varepsilon}{2},
\qquad
\nu(Y \setminus K_Y)<\frac{\varepsilon}{2}.
$$
Then the set $K_X \times K_Y$ is compact in $X \times Y$ and for any $(\gamma_n)\subset \Pi(\mu,\nu)$
$$
\gamma_n\bigl((X \times Y)\setminus (K_X \times K_Y)\bigr)
\leq
\gamma_n\bigl((X \setminus K_X)\times Y\bigr)+\gamma_n\bigl(X \times (Y \setminus K_Y)\bigr)=
\mu(X \setminus K_X)+\nu(Y \setminus K_Y)
<
\frac{\varepsilon}{2}+\frac{\varepsilon}{2}
=
\varepsilon.
$$
Hence $(\gamma_n)$ is tight. Hence by Prokhorov theorem, there exists $\gamma \in \mathcal{P}(X \times Y)$ and a subsequence $(\gamma_{n_k})$ such that
$$
\gamma_{n_k}\rightharpoonup \gamma.
$$

Now, we need to show that $\gamma \in \Pi(\mu,\nu)$. For all $\varphi \in C_b(X)$, since $\gamma_{n_k}\in \Pi(\mu,\nu)$,
$$
\int_{X \times Y} \varphi(x)\ d\gamma_{n_k}(x,y)
=
\int_X \varphi(x)\ d\mu(x).
$$
Let $k \to \infty$, we have
$$
\int_{X \times Y} \varphi(x)\ d\gamma(x,y)
=
\int_X \varphi(x)\ d\mu(x).
$$
Hence $(\pi_x)_\sharp\gamma=\mu$ and similarly $(\pi_y)_\sharp\gamma=\nu$. Therefore, $\gamma \in \Pi(\mu,\nu)$. $\square$

Reference

Santambrogio, Filippo. Optimal transport for applied mathematicians. Birkäuser, NY 55.58-63 (2015): 94.

The cover image of this article was taken in Saipan, Commonwealth of the Northern Mariana Islands (U.S.).