# 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
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. 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
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. Nov 27, 2022 at 10:55
• @JHM I have found a related paper. Please have a check on my below answer. 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.