Return to Answer

The strong Kantorovich duality, i.e. the existence of dual solutions, holds whenever $c$ is lower semicontinuous and real-valued, and the optimal coupling has finite cost, see Theorem 5.10(ii) in Villani "Optimal Transport old and new". In contrast, for the weak duality ("$\inf = \sup$") it suffices to assume $c$ is lower semicontinuous.

To prove 5.10(ii) one constructs an explicit $c$-concave function $\varphi$ that is finite-valued on the support of $\mu$, see formula (5.17). Beware of signs! Villani is looking at $c$-convex functions and you at $c$-concave functions.

To answer the "value part" of the question: the values of $\psi$ and $\varphi$ are only important on the support of $\mu$ and resp. $\nu$. Everywhere else you may choose them to be $-\infty$ (loosing $c$-concavity). Now some cases: If the optimal coupling $\pi$ has cost $1$ then for all $(x,y),(x',y') \in \Gamma := \operatorname{supp}\pi$ it holds $c(x,y')=1$ as otherwise $c(x',y)+c(x,y') < 2 = c(x,y)+c(x',y')$ violating $c$-cyclic monotonicty. Thus $\varphi \equiv 0 \equiv \psi-1$ is a dual solution to the problem. A similar case happens if the cost is $0$ on $\operatorname{supp}\mu \times \operatorname{supp}\nu$. For the last case, pick $(x_0,y_0) \in \Gamma$ with $c(x_0,y_0)=0$ and do the standard construction to get a $c$-concave $\varphi$ with $\varphi(x_0)=0$. Observe if $(x_1,y_1),(x_2,y_2)\in \Gamma$ then

\begin{align*} \varphi(x_{1}) + \psi(x_1) & = c(x_{1},x_{1})\\ \varphi(x_{2}) + \psi(x_2) & = c(x_{2},x_{2}). \end{align*}

Subtracting this from $\varphi+\psi\le c$ applied to the couples $(x_1.y_2)$ and $(x_2,y_1)$ gives \begin{align*} \varphi(x_{2})-\varphi(x_{1}) & \le c(x_{2},y_{1})-c(x_{1},x_{1})\\ \varphi(x_{1})-\varphi(x_{2}) & \le c(x_{1},y_{2})-c(x_{2},y_{2}). \end{align*} The right hand side has values in $\{-1,0,1\}$. Since $\varphi(x_0)=0$ the function $\varphi$ has values in the same set. Since $1-(-1)=2$, it must have values either in $\{0,1\}$ or in $\{-1,0\}$. A similar argument as above then shows that $\psi$ needs have values in $\{-1,0\}$ or $\{0,1\}$.

Note if $c$ is not real-valued then there may not be any dual solutions between certain measures $\mu$ and $\nu$, see the preprint of S. Suhr and me on Lorentzian cost function, more explicitly Section 3.1.

The strong Kantorovich duality, i.e. the existence of dual solutions, holds whenever $c$ is lower semicontinuous and real-valued, and the optimal coupling has finite cost, see Theorem 5.10(ii) in Villani "Optimal Transport old and new". In contrast, for the weak duality ("$\inf = \sup$") it suffices to assume $c$ is lower semicontinuous.

To prove 5.10(ii) one constructs an explicit $c$-concave function $\varphi$ that is finite-valued on the support of $\mu$, see formula (5.17). Beware of signs! Villani is looking at $c$-convex functions and you at $c$-concave functions.

To answer the "value part" of the question: the values of $\psi$ and $\varphi$ are only important on the support of $\mu$ and resp. $\nu$. Everywhere else you may choose them to be $-\infty$ (loosing $c$-concavity). Now some cases: If the optimal coupling $\pi$ has cost $1$ then for all $(x,y),(x',y') \in \Gamma := \operatorname{supp}\pi$ it holds $c(x,y')=1$ as otherwise $c(x',y)+c(x,y') < 2 = c(x,y)+c(x',y')$ violating $c$-cyclic monotonicty. Thus $\varphi \equiv 0 \equiv \psi-1$ is a dual solution to the problem. A similar case happens if the cost is $0$ on $\operatorname{supp}\mu \times \operatorname{supp}\nu$. For the last case, pick $(x_0,y_0) \in \Gamma$ with $c(x_0,y_0)=0$ and do the standard construction to get an integer-valued $c$-concave $\varphi$ with $\varphi(x_0)=0$. Observe if $(x_1,y_1),(x_2,y_2)\in \Gamma$ then

\begin{align*} \varphi(x_{1}) + \psi(x_1) & = c(x_{1},x_{1})\\ \varphi(x_{2}) + \psi(x_2) & = c(x_{2},x_{2}). \end{align*}

Subtracting this from $\varphi+\psi\le c$ applied to the couples $(x_1.y_2)$ and $(x_2,y_1)$ gives \begin{align*} \varphi(x_{2})-\varphi(x_{1}) & \le c(x_{2},y_{1})-c(x_{1},x_{1})\\ \varphi(x_{1})-\varphi(x_{2}) & \le c(x_{1},y_{2})-c(x_{2},y_{2}). \end{align*} The right hand side has values in $\{-1,0,1\}$. Since $\varphi(x_0)=0$ the function $\varphi$ has values in the same set. Since $1-(-1)=2$, it must have values either in $\{0,1\}$ or in $\{-1,0\}$. A similar argument as above then shows that $\psi$ needs have values in $\{-1,0\}$ or $\{0,1\}$.

Note if $c$ is not real-valued then there may not be any dual solutions between certain measures $\mu$ and $\nu$, see the preprint of S. Suhr and me on Lorentzian cost function, more explicitly Section 3.1.

The strong Kantorovich duality, i.e. the existence of dual solutions, holds whenever $c$ is lower semicontinuous and real-valued, and the optimal coupling has finite cost, see Theorem 5.10(ii) in Villani "Optimal Transport old and new". In contrast, for the weak duality ("$\inf = \sup$") it suffices to assume $c$ is lower semicontinuous.

To prove 5.10(ii) one constructs an explicit $c$-concave function $\varphi$ that is finite-valued on the support of $\mu$, see formula (5.17). Beware of signs! Villani is looking at $c$-convex functions and you at $c$-concave functions.

To answer the "value part" of the question: the values of $\psi$ and $\varphi$ are only important on the support of $\mu$ and resp. $\nu$. Everywhere else you may choose them to be $-\infty$ (loosing $c$-concavity). Now some cases: If the optimal coupling $\pi$ has cost $1$ then for all $(x,y),(x',y') \in \Gamma := \operatorname{supp}\pi$ it holds $c(x,y')=1$ as otherwise $c(x',y)+c(x,y') < 2 = c(x,y)+c(x',y')$ violating $c$-cyclic monotonicty. Thus $\varphi \equiv 0 \equiv \psi-1$ is a dual solution to the problem. A similar case happens if the cost is $0$ on $\operatorname{supp}\mu \times \operatorname{supp}\nu$. For the last case, pick $(x_0,y_0) \in \Gamma$ with $c(x_0,y_0)=0$ and do the standard construction to get a $c$-concave $\varphi$ with $\varphi(x_0)=0$. Observe if $(x_1,y_1),(x_2,y_2)\in \Gamma$ then

\begin{align*} \varphi(x_{1}) + \psi(x_1) & = c(x_{1},x_{1})\\ \varphi(x_{2}) + \psi(x_2) & = c(x_{2},x_{2}). \end{align*}

Subtracting this from $\varphi+\psi\le c$ applied to the couples $(x_1.y_2)$ and $(x_2,y_1)$ gives \begin{align*} \varphi(x_{2})-\varphi(x_{1}) & \le c(x_{2},y_{1})-c(x_{1},x_{1})\\ \varphi(x_{1})-\varphi(x_{2}) & \le c(x_{1},y_{2})-c(x_{2},y_{2}). \end{align*} The left hand side has values in $\{-1,0,1\}$. Since $\varphi(x_0)=0$ the function $\varphi$ has values in the same set. Since $1-(-1)=2$, it must have values either in $\{0,1\}$ or in $\{-1,0\}$. A similar argument as above then shows that $\psi$ needs have values in $\{-1,0\}$ or $\{0,1\}$.

Note if $c$ is not real-valued then there may not be any dual solutions between certain measures $\mu$ and $\nu$, see the preprint of S. Suhr and me on Lorentzian cost function, more explicitly Section 3.1.

The strong Kantorovich duality, i.e. the existence of dual solutions, holds whenever $c$ is lower semicontinuous and real-valued, and the optimal coupling has finite cost, see Theorem 5.10(ii) in Villani "Optimal Transport old and new". In contrast, for the weak duality ("$\inf = \sup$") it suffices to assume $c$ is lower semicontinuous.

To prove 5.10(ii) one constructs an explicit $c$-concave function $\varphi$ that is finite-valued on the support of $\mu$, see formula (5.17). Beware of signs! Villani is looking at $c$-convex functions and you at $c$-concave functions.

To answer the "value part" of the question: the values of $\psi$ and $\varphi$ are only important on the support of $\mu$ and resp. $\nu$. Everywhere else you may choose them to be $-\infty$ (loosing $c$-concavity). Now some cases: If the optimal coupling $\pi$ has cost $1$ then for all $(x,y),(x',y') \in \Gamma := \operatorname{supp}\pi$ it holds $c(x,y')=1$ as otherwise $c(x',y)+c(x,y') < 2 = c(x,y)+c(x',y')$ violating $c$-cyclic monotonicty. Thus $\varphi \equiv 0 \equiv \psi-1$ is a dual solution to the problem. A similar case happens if the cost is $0$ on $\operatorname{supp}\mu \times \operatorname{supp}\nu$. For the last case, pick $(x_0,y_0) \in \Gamma$ with $c(x_0,y_0)=0$ and do the standard construction to get a $c$-concave $\varphi$ with $\varphi(x_0)=0$. Observe if $(x_1,y_1),(x_2,y_2)\in \Gamma$ then

\begin{align*} \varphi(x_{1}) + \psi(x_1) & = c(x_{1},x_{1})\\ \varphi(x_{2}) + \psi(x_2) & = c(x_{2},x_{2}). \end{align*}

Subtracting this from $\varphi+\psi\le c$ applied to the couples $(x_1.y_2)$ and $(x_2,y_1)$ gives \begin{align*} \varphi(x_{2})-\varphi(x_{1}) & \le c(x_{2},y_{1})-c(x_{1},x_{1})\\ \varphi(x_{1})-\varphi(x_{2}) & \le c(x_{1},y_{2})-c(x_{2},y_{2}). \end{align*} The right hand side has values in $\{-1,0,1\}$. Since $\varphi(x_0)=0$ the function $\varphi$ has values in the same set. Since $1-(-1)=2$, it must have values either in $\{0,1\}$ or in $\{-1,0\}$. A similar argument as above then shows that $\psi$ needs have values in $\{-1,0\}$ or $\{0,1\}$.

Note if $c$ is not real-valued then there may not be any dual solutions between certain measures $\mu$ and $\nu$, see the preprint of S. Suhr and me on Lorentzian cost function, more explicitly Section 3.1.

The strong Kantorovich duality, i.e. the existence of dual solutions, holds whenever $c$ is lower semicontinuous and real-valued, and the optimal coupling has finite cost, see Theorem 5.10(ii) in Villani "Optimal Transport old and new". In contrast, for the weak duality ("$\inf = \sup$") it suffices to assume $c$ is lower semicontinuous.

To prove 5.10(ii) one constructs an explicit $c$-concave function $\varphi$ that is finite-valued on the support of $\mu$, see formula (5.17). Beware of signs! Villani is looking at $c$-convex functions and you at $c$-concave functions.

To answer the "value part" of the question: the values of $\psi$ and $\varphi$ are only important on the support of $\mu$ and resp. $\nu$. Everywhere else you may choose them to be $-\infty$ (loosing $c$-concavity). Now some cases: If the optimal coupling $\pi$ has cost $1$ then for all $(x,y),(x',y') \in \Gamma := \operatorname{supp}\pi$ it holds $c(x,y')=1$ as otherwise $c(x',y)+c(x,y') < 2 = c(x,y)+c(x',y')$ violating $c$-cyclic monotonicty. Thus $\varphi \equiv 0 \equiv \psi-1$ is a dual solution to the problem. A similar case happens if the cost is $0$ on $\operatorname{supp}\mu \times \operatorname{supp}\nu$. For the last case, pick $(x_0,y_0) \in \Gamma$ with $c(x_0,y_0)=0$ and do the standard construction to get a $c$-concave $\varphi$ with $\varphi(x_0)=0$. Observe if $(x_1,y_1),(x_2,y_2)\in \Gamma$ then
  \begin{align*} \varphi(x_{1})-\varphi(x_{2}) & \le c(x_{1},y_{2})-c(x_{1},x_{1})\\ \varphi(x_{2})-\varphi(x_{1}) & \le c(x_{2},y_{1})-c(x_{2},y_{2}). \end{align*} Since $\varphi(x_0)=0$ the function $\varphi$ has values either in $\{0,1\}$ or in $\{-1,0\}$. A similar argument as above then shows that $\psi$ needs have values in $\{-1,0\}$ or $\{0,1\}$.

Note if $c$ is not real-valued then there may not be any dual solutions between certain measures $\mu$ and $\nu$, see the preprint of S. Suhr and me on Lorentzian cost function, more explicitly Section 3.1.

The strong Kantorovich duality, i.e. the existence of dual solutions, holds whenever $c$ is lower semicontinuous and real-valued, and the optimal coupling has finite cost, see Theorem 5.10(ii) in Villani "Optimal Transport old and new". In contrast, for the weak duality ("$\inf = \sup$") it suffices to assume $c$ is lower semicontinuous.

To prove 5.10(ii) one constructs an explicit $c$-concave function $\varphi$ that is finite-valued on the support of $\mu$, see formula (5.17). Beware of signs! Villani is looking at $c$-convex functions and you at $c$-concave functions.

To answer the "value part" of the question: the values of $\psi$ and $\varphi$ are only important on the support of $\mu$ and resp. $\nu$. Everywhere else you may choose them to be $-\infty$ (loosing $c$-concavity). Now some cases: If the optimal coupling $\pi$ has cost $1$ then for all $(x,y),(x',y') \in \Gamma := \operatorname{supp}\pi$ it holds $c(x,y')=1$ as otherwise $c(x',y)+c(x,y') < 2 = c(x,y)+c(x',y')$ violating $c$-cyclic monotonicty. Thus $\varphi \equiv 0 \equiv \psi-1$ is a dual solution to the problem. A similar case happens if the cost is $0$ on $\operatorname{supp}\mu \times \operatorname{supp}\nu$. For the last case, pick $(x_0,y_0) \in \Gamma$ with $c(x_0,y_0)=0$ and do the standard construction to get a $c$-concave $\varphi$ with $\varphi(x_0)=0$. Observe if $(x_1,y_1),(x_2,y_2)\in \Gamma$ then

\begin{align*} \varphi(x_{1}) + \psi(x_1) & = c(x_{1},x_{1})\\ \varphi(x_{2}) + \psi(x_2) & = c(x_{2},x_{2}). \end{align*}

Subtracting this from $\varphi+\psi\le c$ applied to the couples $(x_1.y_2)$ and $(x_2,y_1)$ gives \begin{align*} \varphi(x_{2})-\varphi(x_{1}) & \le c(x_{2},y_{1})-c(x_{1},x_{1})\\ \varphi(x_{1})-\varphi(x_{2}) & \le c(x_{1},y_{2})-c(x_{2},y_{2}). \end{align*} The left hand side has values in $\{-1,0,1\}$. Since $\varphi(x_0)=0$ the function $\varphi$ has values in the same set. Since $1-(-1)=2$, it must have values either in $\{0,1\}$ or in $\{-1,0\}$. A similar argument as above then shows that $\psi$ needs have values in $\{-1,0\}$ or $\{0,1\}$.

Note if $c$ is not real-valued then there may not be any dual solutions between certain measures $\mu$ and $\nu$, see the preprint of S. Suhr and me on Lorentzian cost function, more explicitly Section 3.1.