Optimal Transport – Existence of 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.