I'm reading the proof of Kantorovich duality from Villani's book Topics in Optimal Transportation.

Let $X$ and $Y$ be Polish spaces. Let $P(X), P(Y)$ be the spaces of all Borel probability measures on $X,Y$ respectively. Let $c: X \times Y \rightarrow \mathbb{R}_{\ge 0} \cup\{+\infty\}$ be lower semi-continuous. Fix $\mu \in P(X)$ and $\nu \in P(Y)$.

  • $\Pi(\mu, \nu)$ is the set of $\pi \in P(X \times Y)$ such that for all measurable subsets $A \subset X$ and $B \subset Y$, $$ \pi[A \times Y]=\mu[A], \quad \pi[X \times B]=\nu[B]. $$

  • $\Phi_{c}$ is the set of all $(\varphi, \psi) \in L^{1}(d \mu) \times L^{1}(d \nu)$ satisfying $$ \varphi(x)+\psi(y) \leq c(x, y) $$ for $\mu$-almost all $x \in X$ and $\nu$-almost all $y \in Y$.

  • For $\pi \in P(X \times Y)$ and $(\varphi, \psi) \in L^{1}(d \mu) \times L^{1}(d \nu)$, let $$I[\pi]:=\int_{X \times Y} c d \pi, \quad J(\varphi, \psi):=\int_{X} \varphi d \mu+\int_{Y} \psi d \nu .$$

Then $$ \inf _{\Pi(\mu, \nu)} I[\pi]=\sup _{\Phi_{c}} J(\varphi, \psi) . $$

The author said that

We separate the proof into three steps, by increasing order of generality. The minimax principle will only be applied in the first step, which is the case when $X$ and $Y$ are compact and $c$ is continuous. All the rest of the proof will consist in showing that this particular case implies the general statement, by approximation arguments.

In the proof below, I could not see how the author uses the continuity of $c$. It seems to me the proof with with the original weaker hypothesis, i.e., $c$ is lower semi-continuous.

Could you elaborate on my confusion?

Proof: It's clear that $$ \sup _{\Phi_{c} \cap C_{b}} J(\varphi, \psi) \leq \sup _{\Phi_{c} \cap L^{1}} J(\varphi, \psi) \leq \inf _{\Pi(\mu, \nu)} I[\pi]. $$

So it remains to prove $$ \inf _{\Pi(\mu, \nu)} I[\pi] \le \sup _{\Phi_{c} \cap C_{b}} J(\varphi, \psi) . $$

To simplify notations, let $\varphi \oplus \psi: (x,y) \mapsto \varphi(x)+\psi(y)$. We have $$ \inf _{\pi \in \Pi(\mu, \nu)} I[\pi]=\inf _{\pi \in M_{+}(X \times Y)}\left(I[\pi]+\left\{\begin{array}{l} 0 \text { if } \pi \in \Pi(\mu, \nu) \\ +\infty \text { else } \end{array}\right)\right. $$ with $M_+(X \times Y)$ the space of non-negative Borel measures on $X\times Y$. Also, $$ \left\{\begin{array}{l} 0 \text { if } \pi \in \Pi(\mu, \nu) \\ +\infty \text { else } \end{array}\right\}=\sup _{(\varphi, \psi)} \left[\int \varphi d \mu+\int \psi d \nu-\int \varphi \oplus \psi d \pi\right], $$ where the supremum on the RHS runs over all $(\varphi, \psi) \in C_b(X) \times C_b(Y)$. It follows that $$ \begin{aligned} \inf _{\pi \in \Pi(\mu, \nu)} I[\pi] =\inf _{\pi \in M_{+}(X \times Y)} \sup _{(\varphi, \psi)} \bigg \{ \int_{X \times Y} c d \pi +\int_{X} \varphi d \mu+\int_{Y} \psi d \nu - \int_{X \times Y} \varphi \oplus \psi d \pi \bigg\}. \end{aligned} $$

  1. Let us first assume that $X, Y$ are compact and that $c$ is continuous on $X \times Y$.
  • Let $E:=C_{b}(X \times Y)$ be the set of all bounded continuous functions on $X \times Y$, equipped with its usual supremum norm $\|\cdot\|_{\infty}$.

  • By Riesz' theorem, the topological dual $E^*$ of $E$ can be identified with the space of regular Radon measures, $M(X \times Y)$, normed by total variation.

  • Moreover, a nonnegative linear form on $E$ corresponds with a regular nonnegative Borel measure.

Then we introduce $$ \begin{gathered} \Theta: u \in E \longmapsto\left\{\begin{array}{l} 0 &\text {if } u \geq-c, \\ +\infty &\text {else}. \end{array}\right.\\ \text{}\\ \Xi: u \in E \longmapsto\left\{\begin{array}{l} \int_{X} \varphi d \mu+\int_{Y} \psi d \nu &\begin{align*} &\text {if } u = \varphi \oplus \psi \text{ for}\\ & \text{some } (\varphi, \psi) \in L^{1}(d \mu) \times L^{1}(d \nu) \end{align*},\\ +\infty &\text {else. } \end{array}\right. \end{gathered} $$

It's easy to verify that $\Theta, \Xi$ satisfy the condition of Fenchel-Rockafellar duality, so $$ \inf _{u\in E}[\Theta(u)+\Xi(u)] = \max _{\pi \in E^{*}}\left[-\Theta^{*}\left(-\pi\right)-\Xi^{*}\left(\pi\right)\right]. $$

It's clear that $$ \begin{align*} \inf _{u\in E}[\Theta(u)+\Xi(u)] &= \inf \left\{\int_{X} \varphi d \mu+\int_{Y} \psi d \nu \,\middle\vert\, (\varphi, \psi) \in L^{1}(d \mu) \times L^{1}(d \nu)\text{ s.t. } \varphi \oplus \psi \geq -c \right\} \\ &=-\sup \left\{J(\varphi, \psi) \mid (\varphi, \psi) \in \Phi_{c}\right\}. \end{align*} $$

Next, we compute the Legendre-Fenchel transforms of $\Theta, \Xi$. First, for any $\pi \in E^*$, $$ \begin{aligned} \Theta^{*}(-\pi) =\sup _{u \in E}\left\{-\int u d \pi \,\middle\vert\, u \geq-c\right\} = \sup _{u \in E}\left\{\int u d \pi \,\middle\vert\, u \leq c\right\} . \end{aligned} $$

  • If $\pi$ is not nonnegative, then there exists a positive function $v \in E$ such that $\int v d \pi<0$. Then, the choice $u=\lambda v$, with $\lambda \rightarrow-\infty$, shows that the supremum is $+\infty$.
  • On the other hand, if $\pi$ is nonnegative, then the supremum is clearly $\int c d \pi$. This is because lower semi-continuous and bounded from below function is a limit of an increasing sequence of Lipschitz continuous functions.

Thus $$ \Theta^{*}(-\pi) = \begin{cases} \int c d \pi &\text {if } \pi \in M_{+}(X \times Y) \\ +\infty &\text {else}. \end{cases} $$

We also have $$ \begin{align*} \Xi^{*}(\pi) &= \sup_{u\in E} \left \{ \int ud\pi - \int \varphi d \mu- \int \psi d\nu \,\middle\vert\, u = \varphi \oplus \psi \text{ for some } (\varphi, \psi) \in L^{1}(d \mu) \times L^{1}(d \nu) \right \} \\ &= \begin{cases} 0 &\text {if } \quad \forall(\varphi, \psi) \in L^{1}(d \mu) \times L^{1}(d \nu) : \int \varphi \oplus \psi d \pi= \int \varphi d \mu+\int \psi d \nu \\ +\infty & \text {else} \end{cases} \\ &= \begin{cases} 0 &\text {if } \quad \pi \in \Pi(\mu, \nu) \\ +\infty & \text {else}. \end{cases} \end{align*} $$

It follows that $$ \max _{\pi \in E^{*}}\left[-\Theta^{*}\left(-\pi\right)-\Xi^{*}\left(\pi\right)\right] = \max _{\pi \in \Pi(\mu, \nu) \cap M_{+}(X \times Y)} -\int c d \pi = - \min _{\pi \in \Pi(\mu, \nu)} \int c d \pi. $$ Hence $$ -\sup \left\{J(\varphi, \psi) \mid (\varphi, \psi) \in \Phi_{c}\right\} = - \min _{\pi \in \Pi(\mu, \nu)} \int c d \pi. $$

  • $\begingroup$ Sorry, I meant my statement to be a comment, not an answer. To understand the Kantorovich--Rubinstein theorem, it's best to realize that its real essence has nothing to do with countable additivity of the measures, or continuity. At its core is a statement about (finitely additive) linear functionals. I don't have a reference handy, but it is a simple exercise, using e.g. the Hahn--Banach theorem, to prove it for finitely additive measures. From that then one gets versions with perfect, Radon, etc. measures, simply because if both marginals are such then so is the measure on the product. $\endgroup$
    – user95282
    May 15, 2022 at 11:15
  • $\begingroup$ A good first step in understanding the K--R theorem is to prove it for finite metric spaces, so that one is not distracted by continuity, measurability etc. $\endgroup$
    – user95282
    May 15, 2022 at 11:33
  • 1
    $\begingroup$ I think your proof works, it's just that at two points (verifying that $\Theta$ is lsc to apply duality, and veryfing $\Theta^*(\pi) = \int c \,d\pi$ for nonnegative $\pi$) is just easier for continuous cost, and thus its reasonable to make this assumption to focus on the big picture of the proof. $\endgroup$
    – Steve
    May 18, 2022 at 8:58


You must log in to answer this question.

Browse other questions tagged .