Duality Results for Kantorovich Problem

In this article, we will prove the duality result for Kantorovich problem.

Theorem 1.8 Suppose that $X$ and $Y$ are Polish spaces, and that $c:X \times Y \to \mathbb{R}$ is uniformly continuous and bounded. Then the problem $(\mathrm{DP})$ admits a solution $(\varphi,\varphi^c)$ and we have
$$
\max (\mathrm{DP}) = \min (\mathrm{KP}).
$$

Proof. Consider the minimization problem $(\mathrm{KP})$. Since $c$ is continuous, it admits a solution $\gamma$. By Theorem 1.7, the support $\Gamma=\operatorname{supp}(\gamma)$ is $c$-cyclically monotone. Since $c$ is real-valued, we can apply Theorem 1.6 and obtain the existence of a $c$-concave function $\varphi$ such that
$$
\Gamma \subset \{(x,y)\in X\times Y:\ \varphi(x)+\varphi^c(y)=c(x,y)\}.
$$

Since $c$ is continuous, we have $\varphi$ and $\varphi^c$ are continuous. Moreover, from the global upper bound on $\varphi^c$, which turns into a lower bound on $\varphi$,

$$
\varphi^c(y)=\inf_{x\in X}[c(x,y)-\varphi(x)].
$$

Symmetrically, we can also obtain upper bounds on $\varphi$ and lower bounds on $\varphi^c$, which proves that $\varphi$ and $\varphi^c$ are both continuous and bounded.

Hence, $(\varphi,\varphi^c)$ can be used as an admissible pair in $(\mathrm{DP})$. Consider now

$$
\int_X \varphi\ d\mu + \int_Y \varphi^c\ d\nu
= \int_{X\times Y} (\varphi(x)+\varphi^c(y))\ d\gamma
= \int_{\operatorname{supp}(\gamma)} (\varphi(x)+\varphi^c(y))\ d\gamma= \int_{\operatorname{supp}(\gamma)} c(x,y)\ d\gamma
= \int_{X\times Y} c(x,y)\ d\gamma.
$$

Hence

$$
(\mathrm{DP})\ge \int_X \varphi\ d\mu+\int_Y \varphi^c\ d\nu
= \int_{X\times Y} c(x,y)\ d\gamma
= (\mathrm{KP}).
$$

Since we already saw $(\mathrm{DP})\le (\mathrm{KP})$, we get $(\mathrm{DP})=(\mathrm{KP})$ and $(\varphi,\varphi^c)$ is optimal for $(\mathrm{DP})$. $\square$

Theorem 1.9 Let $\mu$ and $\nu$ be probability measures over $\mathbb{R}^d$, and $c(x,y):=\frac12|x-y|^2$. Suppose
$$
\int_X |x|^2\ \mu(dx)<+\infty
\qquad\text{and}\qquad
\int_Y |y|^2\ \nu(dy)<+\infty.
$$

Consider the following variant of $(\mathrm{DP})$:

$$
(\mathrm{DP-var})\qquad
\sup\left\{
\int_{\mathbb{R}^d}\varphi\ d\mu+\int_{\mathbb{R}^d}\psi\ d\nu
:\ \varphi\in L^1(\mu),\ \psi\in L^1(\nu),\ \varphi\oplus\psi\le c
\right\}.
$$

Then $(\mathrm{DP-var})$ admits a solution $(\varphi,\psi)$, and the functions

$$
x\mapsto \frac12|x|^2-\varphi(x)
\qquad\text{and}\qquad
y\mapsto \frac12|y|^2-\psi(y)
$$

are convex and conjugate to each other for the Legendre transform. Moreover, we have

$$
\max (\mathrm{DP-var})=\min (\mathrm{KP}).
$$

Proof. Since $c$ is continuous, by Theorem 1.7 the support $\Gamma=\operatorname{supp}(\gamma)$ is $c$-cyclically monotone and then by Theorem 1.6, we get the existence of a pair $(\varphi,\psi)$ with $\psi=\varphi^c$ such that

$$
\varphi(x)+\psi(y)=c(x,y)
\qquad\text{for all }(x,y)\in \Gamma.
$$

From Proposition 1.2, we know

$$
x\mapsto \frac12|x|^2-\varphi(x),\qquad
y\mapsto \frac12|y|^2-\psi(y)
$$

are convex and conjugate to each other, hence bounded from below by a linear function; hence $\varphi$ and $\psi$ are bounded by a second order polynomial. Since

$$
\int_X |x|^2\ d\mu<+\infty
\qquad\text{and}\qquad
\int_Y |y|^2\ d\nu<+\infty,
$$

we know $\varphi_+\in L^1(\mu)$ and $\psi_+\in L^1(\nu)$.

Since

$$
\int_{\mathbb{R}^d}\varphi\ d\mu+\int_{\mathbb{R}^d}\psi\ d\nu
=
\int_{\mathbb{R}^d\times\mathbb{R}^d} \varphi\oplus\psi\ d\gamma
=
\int_{\mathbb{R}^d\times\mathbb{R}^d} c(x,y)\ d\gamma
\ge 0,
$$

this proves

$$
\int_{\mathbb{R}^d}\varphi\ d\mu,\ \int_{\mathbb{R}^d}\psi\ d\nu >-\infty.
$$

Hence $\varphi\in L^1(\mu)$, $\psi\in L^1(\nu)$.

Therefore

$$
\sup(\mathrm{DP-var})\ge
\int_{\mathbb{R}^d}\varphi\ d\mu+\int_{\mathbb{R}^d}\psi\ d\nu
=
\int_{\mathbb{R}^d\times\mathbb{R}^d} c(x,y)\ d\gamma
=
\min(\mathrm{KP}).
$$

However, by $\varphi\oplus\psi\le c$, we know $\sup(\mathrm{DP-var})\le \min(\mathrm{KP})$. We get

$$
\max(\mathrm{DP-var})=\min(\mathrm{KP})
$$

and $(\varphi,\psi)$ is the solution of $(\mathrm{DP-var})$. $\square$

Lemma 1.8 Suppose that $c_k$ and $c$ are lower semi-continuous, and bounded from below and that $c_k$ converges increasingly to $c$. Then
$$
\lim_{k\to\infty}\min\left\{\int_{X\times Y} c_k\ d\gamma:\ \gamma\in\Pi(\mu,\nu)\right\}
=
\min\left\{\int_{X\times Y} c\ d\gamma:\ \gamma\in\Pi(\mu,\nu)\right\}.
$$

Proof. Since $c_k\le c$, it is obvious that $LHS\le RHS$.

Now consider a sequence $\gamma_k\in\Pi(\mu,\nu)$ which is the minimizer for each cost $c_k$.

Up to subsequences, due to the tightness of $\Pi(\mu,\nu)$, we can suppose

$$
\gamma_k \rightharpoonup \overline{\gamma}.
$$

Fix now an index $j$. Since for $k\ge j$ we have $c_k\ge c_j$, and then

$$
\lim_k \min\left\{\int_{X\times Y} c_k\ d\gamma:\ \gamma\in\Pi(\mu,\nu)\right\}
=
\lim_k \int_{X\times Y} c_k\ d\gamma_k
\ge
\liminf_k \int_{X\times Y} c_j\ d\gamma_k.
$$

Since $c_j$ is lower semi-continuous, and $\gamma_k\rightharpoonup \overline{\gamma}$,

$$
\liminf_k \int_{X\times Y} c_j\ d\gamma_k
\ge
\int_{X\times Y} c_j\ d\overline{\gamma}.
$$

Hence, we obtain

$$
\lim_k \min\left\{\int_{X\times Y} c_k\ d\gamma:\ \gamma\in\Pi(\mu,\nu)\right\}
\ge
\int_{X\times Y} c_j\ d\overline{\gamma}.
$$

Since $j$ is arbitrary and

$$
\lim_{j\to\infty}\int_{X\times Y} c_j\ d\overline{\gamma}
=
\int_{X\times Y} c\ d\overline{\gamma}
$$

by monotone convergence theorem, we also have

$$
\lim_k \min\left\{\int_{X\times Y} c_k\ d\gamma:\ \gamma\in\Pi(\mu,\nu)\right\}
\ge
\int_{X\times Y} c\ d\overline{\gamma}
\ge
\min\left\{\int_{X\times Y} c\ d\gamma:\ \gamma\in\Pi(\mu,\nu)\right\}.
$$

This completes the proof and $\overline{\gamma}$ is optimal for cost $c$. $\square$

Theorem 1.10 If $X,Y$ are Polish spaces and $c:X\times Y\to \mathbb{R}\cup\{+\infty\}$ is lower semi-continuous and bounded from below, then the duality formula
$$
\min(\mathrm{KP})=\sup(\mathrm{DP})
$$

holds.

Proof. Consider a sequence $c_k$ of bounded $k$-Lipschitz functions approaching $c$ increasingly. Then the dual result holds for $c_k$ and then

$$
\min\left\{\int_{X\times Y} c_k\ d\gamma:\ \gamma\in\Pi(\mu,\nu)\right\}
=
\max\left\{
\int_X \varphi\ d\mu+\int_Y \psi\ d\nu:\ \varphi\in C_b(X),\ \psi\in C_b(Y),\ \varphi\oplus\psi\le c_k
\right\}\le
\sup\left\{
\int_X \varphi\ d\mu+\int_Y \psi\ d\nu:\ \varphi\oplus\psi\le c
\right\}.
$$

Let $k\to\infty$, by Lemma 1.8, we get the desired result. $\square$

Remark: For the cost $c$, we can not guarantee the existence of a maximizing pair $(\varphi,\psi)$.

Theorem 1.11 If $c$ is lower semi-continuous and $\gamma$ is an optimal transport plan, then $\gamma$ is concentrated on a $c$-CM set $\Gamma$.

Proof. By Theorem 1.10, we can take a sequence of maximizing pairs $(\varphi_n,\psi_n)$ in the dual problem, we have

$$
\int_{X\times Y} (\varphi_n(x)+\psi_n(y))\ d\gamma
=
\int_X \varphi_n(x)\ d\mu+\int_Y \psi_n(y)\ d\nu
\to
\int_{X\times Y} c\ d\gamma,
$$

where $\gamma$ is optimal for $c$.

Moreover, since

$$
f_n(x,y):=c(x,y)-\varphi_n(x)-\psi_n(y)\ge 0,
$$

we have

$$
\int_{X\times Y} |f_n(x,y)|\ d\gamma
=
\int_{X\times Y} f_n(x,y)\ d\gamma
\to 0
\qquad\text{as }n\to\infty,
$$

that is $f_n\to 0$ in $L^1(X\times Y,\gamma)$. Therefore, up to a subsequence, they also converge pointwisely $\gamma$-a.e. to $0$. Let $\Gamma\subset X\times Y$ be the set with $\gamma(\Gamma)=1$, where the convergence holds.

Take any $k$, $\sigma$ and $(x_1,y_1),\cdots,(x_k,y_k)\in \Gamma$, we have

$$
\sum_{i=1}^k c(x_i,y_i)
=
\lim_{n\to\infty}\sum_{i=1}^k(\varphi_n(x_i)+\psi_n(y_i))
=
\lim_{n\to\infty}\sum_{i=1}^k(\varphi_n(x_i)+\psi_n(y_{\sigma(i)}))
\le
\sum_{i=1}^k c(x_i,y_{\sigma(i)}),
$$

which proves that $\Gamma$ is $c$-CM. $\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 from the Luzern–Interlaken Express while passing Lake Lungern in Switzerland.