Skip to main content
added 143 characters in body
Source Link
Akira
  • 825
  • 2
  • 9
  • 16

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. $$

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$.

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. $$

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. $$

added 106 characters in body
Source Link
Akira
  • 825
  • 2
  • 9
  • 16

The significance What is the role of of continuity in thethis proof of Kantorovich duality?

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$.

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. $$

The significance of continuity in the proof of Kantorovich duality

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$. 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$.

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. $$

What is the role of of continuity in this proof of Kantorovich duality?

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$.

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. $$

Source Link
Akira
  • 825
  • 2
  • 9
  • 16

The significance of continuity in the proof of Kantorovich duality

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$. 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$.

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. $$