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?
Best Answer
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)$.