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?


1 Answer 1


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)$.

  • $\begingroup$ Thank you so much for your help! I think you meant $\sum_{i=0}^{n-1}$ rather than $\sum_{i=1}^{n-1}$. $\endgroup$
    – Analyst
    Jul 27 at 2:05
  • $\begingroup$ You are right, corrected. $\endgroup$
    – Steve
    Jul 27 at 5:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.