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

$$\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!

• I don't think anybody knows how to prove "from foundations" the measurability of the c-concave potentials. But it's better to specialize to costs which satisfy (Twist) conditions, then you more readily obtain the uniform semiconcavity, local Lipschitz constants, etc, of the potentials. In practice it's better to first obtain the almost-everywhere differentiability of the potentials by differentiating along the graph of the c-subdifferentials, from $c(x,y)=-\phi(x)+\psi(y)$ to $\nabla_x c(x,y) = - \nabla_x \phi(x).$
– JHM
Commented Nov 21, 2022 at 14:09
• @JHM It seems from your comment that Exercise 2.36 has no solution... I would like to send an email to Villani but I could not find his email address. Commented Nov 21, 2022 at 14:18
• Theorem 5.10, pp.57 from Villani's Old and New is the relevant theorem for existence of maximizing potentials. But "measurability" of the potentials comes more readily as consequence of (Twist). In OT i think it's more useful to be specific about your costs and your measures, and not attempt to maintain "max generality". For example, measurability of what potentials on what type of spaces relative to what type of costs? The regularity of the potentials is typically "inherited" from the regularity of the cost function $c: X\times Y \to \bf{R}$.
– JHM
Commented Nov 27, 2022 at 6:18
• @JHM If $c$ is continuous then $\varphi^c$ is upper semi-continuous and thus measurable. From the condition $c(x,y) \le c_X (x) + c_Y(y) \quad \forall (x, y) \in X \times Y$, we can prove that $\varphi^c$ is also $\nu$-integrable. Of course, $c$ being continuous is sufficient for most applications. In this thread, I'm curious about the machinery that allows the author to obtain the result in case $c$ is just lower semi-continuous. Commented Nov 27, 2022 at 10:55
• @JHM I have found a related paper. Please have a check on my below answer. Commented Dec 15, 2022 at 14:46

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.

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.