Optimal transport: the existence of an optimal pair of $c$-conjugate functions

Question

$\newcommand{\diff}{ \, \mathrm d}$

Let

• $X,Y$ be Polish spaces,
• $\mathcal C_b(X)$ the space of all real-valued bounded continuous functions on $X$,
• $\mathcal P(X)$ the space of Borel probability measures on $X$,
• $\mu \in \mathcal P(X)$ and $\nu \in \mathcal P(Y)$.
• $L_1 (\mu)$ the space of all $\mu$-integrable functions $\varphi:X \to \mathbb R \cup \{-\infty\}$,
• $\Pi(\mu, \nu)$ a subset of $\mathcal P(X \times Y)$ that contains all measures whose marginal on $X$ is $\mu$ and that on $Y$ is $\nu$, and
• $c:X \times Y \to [0, +\infty]$ measurable.

Let $\Phi_c$ (resp. $\Phi'_c$) be the collection of all $(\varphi, \psi) \in \mathcal C_b(X) \times \mathcal C_b(Y)$ (resp. $(\varphi, \psi) \in L_1 (\mu) \times L_1 (\nu)$) such that $\varphi (x)+\psi(y) \le c(x, y)$ for all $(x,y) \in X \times Y$. Let $$ \begin{align} \mathbb J (\varphi, \psi) &:= \int \varphi \diff \mu + \int \psi \diff \nu &&\forall (\varphi, \psi) \in L_1(\mu) \times L_1(\nu),\\ \mathbb K (\gamma) &:= \int c \diff \gamma &&\forall \gamma \in \Pi(\mu, \nu). \end{align} $$

The Kantorovich and its dual problems are $$ \begin{align} (\mathrm{KP}) &: \quad \inf \left \{ \mathbb K (\gamma) : \gamma \in \Pi(\mu, \nu) \right \}, \\ (\mathrm{DP}) &: \quad \sup \left \{ \mathbb J (\varphi, \psi) : (\varphi, \psi) \in \Phi_c \right \}, \\ (\mathrm{DP'}) &: \quad \sup \left \{ \mathbb J (\varphi, \psi) : (\varphi, \psi) \in \Phi'_c \right \}. \end{align} $$

Clearly, $$ \Phi_c \subset \Phi_c' \quad \text{and} \quad \sup \mathrm{DP} \le \sup \mathrm{DP'} \le \inf \mathrm{KP}. $$

The central definition leading to the existence of solutions of above problems is $c$-concavity, i.e.,

Definition 2.33 A function $\varphi: X \rightarrow \mathbb{R} \cup\{-\infty\}$ is said to be $c$-concave if there exists $\psi: Y \to \mathbb{R} \cup\{-\infty\}$ such that $\psi \not \equiv-\infty$ and that $$ \varphi(x) = \psi^c (x) := \inf _{y \in Y}[c(x, y)-\psi(y)] \quad \forall x \in X. $$ Here $\varphi$ is called the $c$-conjugate of $\varphi$.

I'm able to prove that

Theorem Let $c$ be real-valued and lower semi-continuous. Assume there exists $(c_X, c_Y) \in L_1 (\mu) \times L_1(\nu)$ such that they are real-valued and that $c(x,y) \le c_X(x) + c_Y (y)$ for all $(x,y) \in X \times Y$. Then $\mathrm{DP'}$ admits a solution.

At the bottom of page 87 of Villani's Topics in Optimal Transport, there is Exercise 2.36 to prove that $\mathrm{DP'}$ admits a maximizer, i.e.,

Exercise 2.36 Let $c$ be lower semi-continuous. Assume there exists $(c_X, c_Y) \in L_1 (\mu) \times L_1 (\nu)$ that are non-negative such that $$c(x,y) \le c_X (x) + c_Y(y) \quad \forall (x, y) \in X \times Y.$$ Then $\mathrm{DP'}$ admits a solution of the form $(\varphi, \varphi^c) \in \Phi_c'$.

My attempt: To make it easier, for Exercise 2.36 I assumer further that $c, c_X, c_Y$ are real-valued. By Theorem, $\mathrm{DP'}$ admits a solution $(\varphi, \psi) \in \Phi'_c$. Now we assume that $\varphi^c \in L_1 (\nu)$. By definition, $$ \varphi^c (y) \le c(x, y)-\varphi(x) \quad \forall (x, y) \in X \times Y. $$

So $(\varphi, \varphi^c) \in \Phi'_c$. Also, $$ \varphi^c (y) = \inf_{x \in X} (c(x, y)-\varphi(x)) \ge \inf_{x \in X} (\psi (y)) = \psi (y). $$

So $\mathbb J (\varphi, \varphi^c) \ge \mathbb J (\varphi, \psi)$. Then $(\varphi, \varphi^c)$ satisfies the requirement. This is called by the author as double convexification trick.

---

My question: The first issue is to prove that $\varphi^c$ is measurable, and the second one is to prove that $\varphi^c$ is $\nu$-integrable. However, the measurability of $\varphi^c$ is subtle and non-trivial. Above exercise is exactly Theorem 4.10 in this lecture note in which the measurability of $\varphi^c$ is not proved.

In optimal transport, this is a fundamental result in both theory and practice. Could you elaborate on how to finish Exercise 2.36?

Thank you so much for your elaboration!

Answer 1

I have found a related paper Existence and stability results in the $L^1$ theory of optimal transportation by Luigi Ambrosio and Aldo Pratelli. Step 2 of the proof of Theorem 3.2 is

Step 2. Now we show that $\psi:=\varphi^c$ is $\nu$-measurable, real-valued $\nu$-a.e. and that $$ \varphi+\psi=c \text { on } \Gamma \text {. } $$ It suffices to study $\psi$ on $\pi_Y(\Gamma)$ : indeed, as $\gamma$ is concentrated on $\Gamma$, the Borel set $\pi_Y(\Gamma)$ has full measure with respect to $\nu=\pi_{Y \#} \gamma$. For $y \in \pi_Y(\Gamma)$ we notice that $(10)$ gives $$ \psi(y)=c(x, y)-\varphi(x) \in \mathbb{R} \quad \forall x \in \Gamma_y:=\{x:(x, y) \in \Gamma\} $$ In order to show that $\psi$ is $\nu$-measurable we use the disintegration $\gamma=\gamma_y \otimes \nu$ of $\gamma$ with respect to $y$ (see the appendix) and notice that the probability measure $\gamma_y$ is concentrated on $\Gamma_y$ for $\nu$-a.e. $y$, therefore $$ \psi(y)=\int_X c(x, y)-\varphi(x) d \gamma_y(x) \quad \text { for } \nu \text {-a.e. } y $$ Since $y \mapsto \gamma_y$ is a Borel measure-valued map we obtain that $\psi$ is $\nu$-measurable.

In the proof, $\psi$ is proved to be $\nu$-measurable. It seems to me being $\nu$-measurable is equivalent to being Bochner measurable, i.e., $\psi$ is a $\nu$-a.e. pointwise limit of a sequence of simple functions. So $\psi$ is $not$ necessarily Borel measurable.

Answer 2

I was also struggling with Exercise 2.36... I think that I am now able to solve it, although it seems that it is more difficult than it appears...

The key seems to be the following theorem.

Theorem: Let $X$, $Y$ be Polish spaces and let $\mu$ be a probability measure on (the Borel $\sigma$-algebra of) $X$. Further, let $\varphi \colon X \to [-\infty,\infty)$ be a Borel measurable function and let $c \colon X \times Y \to [0,\infty]$ be lower semicontinuous. Then, there exists a Borel measurable set $N \subset X$ with $\mu(N) = 0$ such that $\psi \colon Y \to [-\infty,\infty]$ defined via $$ \psi(y) := \inf\{ c(x,y) - \varphi(x) \mid x \in X \setminus N\} $$ is measurable. Equivalently, we can redefine $\varphi$ to take the value $-\infty$ on $N$ and then, $\varphi^c$ is measurable.

This theorem seems to be quite versatile. I am quite surprised that I was not able to found a similar assertions in books on optimal transport.

Proof: Using the tightness and inner regularity of $\mu$ and Lusin's theorem, we find an increasing sequence of compact sets $K_n \subset X$ with $\mu(X \setminus K_n) \le 1/n$ such that $\varphi$ is continuous on $K_n$. We define $N := X \setminus \bigcup_{n \in \mathbb N} K_n$.

We fix a sequence $c_m \colon X \times Y \to \mathbb R$ of continuous functions such that $c_m$ converges pointwise and monotonously increasing towards $c$.

We define functions $\psi_n, \psi_{n,m} \colon Y \to [-\infty,\infty]$ via \begin{align*} \psi_n(y) &:= \inf\{ c(x,y) - \varphi(x) \mid x \in K_n \}, \\ \psi_{n,m}(y) &:= \inf\{ c_m(x,y) - \varphi(x) \mid x \in K_n\}. \end{align*} Clearly, $\psi_{n,m}$ is upper semicontinuous, thus Borel measurable. Let us check that $\psi_{n,m}$ converges pointwise towards $\psi_n$. Indeed, let $x_{y,n,m}$ denote the minimizer of $$ K_n \ni x \mapsto c_m(x,y) - \varphi(x). $$ By compactness, we know $x_{y,n,m} \to x_{y,n}$ as $m \to \infty$ along a subsequence. For $M < c(x_{y,n},y) - \varphi(x_{y,n})$ there exists $m_0$ with $$ c_{m_0}(x_{y,n},y) - \varphi(x_{y,n}) > M.$$ From the convergence $x_{y,n,m} \to x_{y,n}$ and the continuity of $c_{m_0}$ and $\varphi$ (on $K_n$), we get $$ c_{m_0}(x_{y,n,m},y) - \varphi(x_{y,n,m}) > M$$ for $m$ (from the subsequence) large enough. The monotone convergence ensures $$ \psi_{n,m}(y) = c_{m}(x_{y,n,m},y) - \varphi(x_{y,n,m}) > M$$ for $m$ (from the subsequence) large enough. This shows $$ \limsup_{m \to \infty} \psi_{n,m}(y) \ge c(x_{y,n}, y) - \varphi(x_{y,n}) \ge \psi_n(y).$$ The reverse inequality follows from $c_m \le c$ and since $\psi_{n,m}(y)$ is increasing in $m$, the limit superior is actually a limit. Thus, $$ \lim_{m \to \infty} \psi_{n,m}(y) = \psi_n(y) \qquad\forall y \in Y.$$ Consequently, $\psi_n$ is Borel measurable. Finally, $\psi_n(y)$ is decreasing for every $y \in Y$ and \begin{align*} \lim_{n \to\infty} \psi_n(y) &= \inf\{ \psi_n(y) \mid n \in \mathbb N \} \\&= \inf\{ c(x,y) - \varphi(y) \mid x \in K_n, n \in \mathbb N\} \\&= \inf\{ c(x,y) - \varphi(y) \mid x \in \bigcup_{n\in\mathbb N} K_n\} \\&= \psi(y)\end{align*} for all $y \in Y$. Consequently, $\psi$ is measurable and this finishes the proof.