# Optimal transport for applied mathematicians: how does $\varphi (x) = \inf_{y \in Y} [c(x, y) - \psi (y)] \neq -\infty$ follow in Theorem 1.37?

I'm reading a proof of Theorem 1.37 from Santambrogio's Optimal transport for applied mathematicians: calculus of variations, PDEs, and modeling. First, I quote related definitions. Let $$X,Y$$ be Polish spaces and $$\overline{\mathbb{R}} := \mathbb R \cup \{\pm \infty\}$$.

• Definition 1.10. Given a function $$\chi: X \rightarrow \overline{\mathbb{R}}$$ we define its $$c$$-transform $$\chi^{c}: Y \rightarrow \overline{\mathbb{R}}$$ by $$\chi^{c}(y)=\inf _{x \in X} c(x, y)-\chi(x)$$. We also define the $$\bar{c}$$-transform of $$\zeta: Y \rightarrow \overline{\mathbb{R}}$$ by $$\zeta^{\bar{c}}(x)=\inf _{y \in Y} c(x, y)-\zeta(y)$$. Moreover, a function $$\psi$$ defined on $$Y$$ is $$\bar{c}$$-concave if there exists $$\chi$$ such that $$\psi=\chi^{c}$$ (and, analogously, a function $$\varphi$$ on $$X$$ is said to be $$c$$-concave if there is $$\zeta: Y \rightarrow \overline{\mathbb{R}}$$ such that $$\left.\varphi=\zeta^{\bar{c}}\right)$$.

• Definition 1.36. Once a function $$c: \Omega \times \Omega \rightarrow \mathbb{R} \cup\{+\infty\}$$ is given, we say that a set $$\Gamma \subset$$ $$\Omega \times \Omega$$ is $$c$$-cyclically monotone (briefly $$c$$-CM) if, for every $$k \in \mathbb{N}$$, every permutation $$\sigma$$ and every finite family of points $$\left(x_{1}, y_{1}\right), \ldots,\left(x_{k}, y_{k}\right) \in \Gamma$$ we have $$\sum_{i=1}^{k} c\left(x_{i}, y_{i}\right) \leq \sum_{i=1}^{k} c\left(x_{i}, y_{\sigma(i)}\right).$$

Below is the theorem of my interest.

Theorem 1.37. If $$\Gamma \neq \emptyset$$ is a $$c$$-CM set in $$X \times Y$$ and $$c: X \times Y \rightarrow \mathbb{R}$$ (note that $$c$$ is required not to take the value $$+\infty)$$, then there exists a c-concave function $$\varphi: X \rightarrow$$ $$\mathbb{R} \cup\{-\infty\}$$ (different from the constant $$-\infty$$ function) such that $$\Gamma \subset\left\{(x, y) \in X \times Y: \varphi(x)+\varphi^{c}(y)=c(x, y)\right\}.$$

Proof. We will give an explicit formula for the function $$\varphi$$, prove that it is well-defined and that it satisfies the properties that we want to impose. Let us fix a point $$\left(x_{0}, y_{0}\right) \in \Gamma:$$ for $$x \in X$$ set \begin{aligned} \varphi(x)=\inf \left\{c\left(x, y_{n}\right)\right.&-c\left(x_{n}, y_{n}\right)+c\left(x_{n}, y_{n-1}\right)-c\left(x_{n-1}, y_{n-1}\right)+\cdots+\\ &\left.+c\left(x_{1}, y_{0}\right)-c\left(x_{0}, y_{0}\right): n \in \mathbb{N},\left(x_{i}, y_{i}\right) \in \Gamma \text { for all } i=1, \ldots, n\right\} \end{aligned} Since $$c$$ is real-valued and $$\Gamma$$ is non-empty, $$\varphi$$ never takes the value $$+\infty$$. If we set, for $$y \in Y$$, \begin{aligned} -\psi(y)=\inf \left\{-c\left(x_{n}, y\right)\right.&+c\left(x_{n}, y_{n-1}\right)-c\left(x_{n-1}, y_{n-1}\right)+\cdots+c\left(x_{1}, y_{0}\right)+ \\ &\left.-c\left(x_{0}, y_{0}\right): n \in \mathbb{N},\left(x_{i}, y_{i}\right) \in \Gamma \text { for all } i=1, \ldots, n, y_{n}=y\right\} . \end{aligned}

Note that from the definition we have $$\psi(y)>-\infty$$ if and only if $$y \in\left(\pi_{y}\right)(\Gamma)$$. Moreover, by construction we have $$\varphi=\psi^{\bar{c}}$$. This proves that $$\varphi$$ is $$c$$-concave $${ }^{8}$$. The fact that $$\varphi$$ is not constantly $$-\infty$$ can be seen from $$\varphi\left(x_{0}\right) \geq 0$$ : indeed, if we take $$x=x_{0}$$, then for any chain of points $$\left(x_{i}, y_{i}\right) \in \Gamma$$ we have $$\sum_{i=0}^{n} c\left(x_{i+1}, y_{i}\right) \geq \sum_{i=0}^{n} c\left(x_{i}, y_{i}\right)$$ where we consider $$x_{n+1}=x_{0}$$. This shows that the infimum in the definition of $$\varphi\left(x_{0}\right)$$ is non-negative.

To prove $$\varphi(x)+\varphi^{c}(y)=c(x, y)$$ on $$\Gamma$$ it is enough to prove the inequality $$\varphi(x)+$$ $$\varphi^{c}(y) \geq c(x, y)$$ on the same set, since by definition of $$c$$-transform the opposite inequality is always true. Moreover, since $$\varphi^{c}=\psi^{\bar{c} c}$$ and $$\psi^{\bar{c} c} \geq \psi$$, it is enough to check $$\varphi(x)+\psi(y) \geq c(x, y)$$

Suppose $$(x, y) \in \Gamma$$ and fix $$\varepsilon>0$$. From $$\varphi=\psi^{\bar{c}}$$ one can find a point $$\bar{y} \in \pi_{y}(\Gamma)$$ such that $$\color{blue}{c(x, \bar{y})-\psi(\bar{y})<\varphi(x)+\varepsilon}$$. In particular, $$\psi(\bar{y}) \neq \pm \infty$$. From the definition of $$\psi$$ one has the inequality $$-\psi(y) \leq-c(x, y)+c(x, \bar{y})-\psi(\bar{y})$$ (since every chain starting from $$\bar{y}$$ may be completed adding the point $$(x, y) \in \Gamma)$$.

Putting together these two informations one gets $$-\psi(y) \leq-c(x, y)+c(x, \bar{y})-\psi(\bar{y})<-c(x, y)+\varphi(x)+\varepsilon,$$ which implies the inequality $$c(x, y) \leq \varphi(x)+\psi(y)$$ since $$\varepsilon$$ is arbitrary.

My question: In previous paragraphs, the author said that

• $$\varphi: X \to \mathbb R \cup \{-\infty\}$$ is proper, i.e., $$\varphi$$ is not identical to $$-\infty$$. In particular, $$\varphi (x_0) \ge 0$$.
• $$\psi(y) \neq -\infty$$ if and only if $$y \in \pi_{y} (\Gamma)$$ where $$\pi_{y}:X \times Y \to Y$$ is the projection map.

My concern lies within the sentence

Suppose $$(x, y) \in \Gamma$$ and fix $$\varepsilon>0$$. From $$\varphi=\psi^{\bar{c}}$$ one can find a point $$\bar{y} \in \pi_{y}(\Gamma)$$ such that $$\color{blue}{c(x, \bar{y})-\psi(\bar{y})<\varphi(x)+\varepsilon}$$.

With $$x_{n+1} := x_0$$, we have \begin{align} \varphi (x) &:= \inf \left \{ c(x, y_n) - c (x_n, y_n) + \sum_{i=0}^{n-1} [ c(x_{i+1}, y_i) - c(x_{i}, y_i) ] \,\middle\vert\, n \in \mathbb N^*,(x_i, y_i)_{i=1}^n \subset \Gamma \right \} \\ &= \inf \left \{ c(x, y_n) -c(x_0, y_n) + \sum_{i=0}^{n} [ c(x_{i+1}, y_i) - c(x_{i}, y_i) ] \,\middle\vert\, n \in \mathbb N^*,(x_i, y_i)_{i=1}^n \subset \Gamma \right \}. \end{align}

Notice that $$(x_i, y_i)_{i=0}^n \subset \Gamma$$, so $$\sum_{i=0}^{n} [ c(x_{i+1}, y_i) - c(x_{i}, y_i) ] \ge 0$$. Then we have an estimate $$\varphi (x) \ge \inf \{ c(x, y_n) -c(x_0, y_n) \mid y_n \in \pi_{y} (\Gamma)\}.$$

As the author said $$\varphi (x) = \psi^{\bar{c}} (x) = \inf_{y \in Y} [c(x, y) - \psi (y)].$$

Then I think the inequality $$\color{blue}{c(x, \bar{y})-\psi(\bar{y})<\varphi(x)+\varepsilon}$$ is only valid if $$\varphi (x) \neq -\infty$$. But I could not get how $$\varphi (x) \neq -\infty$$ in case $$(x, y) \in \Gamma$$. Could you elaborate on my confusion?

I hope I did not misunderstand the question, but it seems $$\varphi(x) > - \infty$$ holds as follows if $$(x, y) \in \Gamma$$:
For any $$(x_i, y_i) \in \Gamma$$, $$i=1, \dots, n$$, we see that \begin{align} &c(x, y_{n}) - c(x_n, y_n) + \sum_{i=0}^{n-1} c(x_{i+1}, y_i) - c(x_i, y_i) \\ &= c(x, y_{n}) - c(x_n, y_n) + \sum_{i=0}^{n-1} c(x_{i+1}, y_i) - c(x_i, y_i) \\&+ c(x_0, y) - c(x, y) -c(x_0, y) + c(x, y) \\ &= - c(x, y) + c(x, y_n) - c(x_n, y_n) + c(x_n, y_{n-1}) - ... + c(x_1, y_0) - c(x_0, y_0) + c(x_0, y) \\ &+c(x, y) - c(x_0, y) \\ &\geq c(x, y) - c(x_0, y) > -\infty, \end{align} where the last inequality holds since $$(x, y) \in \Gamma$$ and by $$c$$-cyclical monotonicity of $$\Gamma$$. Thus, $$\varphi(x)$$ is bounded from below by $$c(x, y) - c(x_0, y)$$.
• Thank you so much for your help! I think you meant $\sum_{i=0}^{n-1}$ rather than $\sum_{i=1}^{n-1}$. Jul 27, 2022 at 2:05