Consider the uniform distribution $\lambda$ on $[0,1]$, and a point measure $\rho$ with density $\frac{1}{2} (\delta_{x_1} + \delta_{x_2})$, where we have $0\le x_1 \le x_2 < 1/2$.

If our cost is just the distance $c(x,y) = | x - y|$, it seems reasonably clear that the optimal transport map from $\lambda$ to $\rho$ would be $$ T(x) = \begin{cases} x_1 & \text{if } x < 1/2\\ x_2 & \text{if } x \ge 1/2 \end{cases} $$ and the optimal coupling would have density along the lines of $$ \mathrm{d}\pi(x,y) = \frac{1}{2} \left( \chi_{[0,1/2)}(x) \delta_{x_1}(y) + \chi_{[1/2,1]}(x) \delta_{x_2}(y)\right), $$ where $\chi_{A}$ is an indicator function. However, consider the usual Kantorovich dual formulation where we want to find $$ \sup_{\phi, \psi} \left( \int_0^1 \phi(y) \, \mathrm{d}y - \frac{1}{2}(\psi_1 + \psi_2)\right) = \sup_{\psi} \left( \int_0^1 \psi^c(y) \, \mathrm{d}y - \frac{1}{2}(\psi_1 + \psi_2)\right) $$ where the supremum is taken over all 1-Lipschitz functions $\phi$ and $\psi = \{ \psi_1,\psi_2\}$ such that $| \psi_1 - \psi_2 | \le | x_1 - x_2 |$, and where $\phi(y) - \psi_i \le |x_i - y|$. Furthermore $\psi^c$ is the usual $c$-transform, which in this case is $$ \psi^c(y) = \min_{i} \left(\psi_i + | x_i - y |\right). $$ (There is some abuse of notation here BTW)

My problem is: This dual solution doesn't seem to work in this case. Ideally we want Laguerre cells $$ \mathrm{Lag}_1 := \{ x : |x - x_1| + \psi_1 \le |x - x_2| + \psi_2, \,\, \forall j \neq i\} = [0,1/2), $$ and similarly $\mathrm{Lag}_2 = [1/2,1]$. I just can't see how we can find values $\psi_1, \psi_2$ that give us these Laguerre cells. If say $\psi_2 = \psi_1 + \varepsilon$ where $\varepsilon < x_2 - x_1$, then $\psi$ would be "$c$-convex" and we would get $$ \mathrm{Lag}_1 = [0, (x_2 - x_1 + \varepsilon)/2) $$ which obviously has measure of less than $1/2$. If $\varepsilon > x_2 - x_1$ then we'd have that $\mathrm{Lag}_1 = [0,1]$ and $\mathrm{Lag}_2 = \emptyset$, and furthermore it seems that $\psi$ would not be $c$-convex any more.

Am I missing something here? I can't see in the theory (e.g. Theorem 5.10 from Villani's Optimal Transport: Old and New) why we wouldn't be able to have a dual form in this example. Also in the question On semi-discrete Wasserstein distance there is a similar issue: you can see that the green points are not contained within their respective Laguerre cells, which may mean it is similarly impossible to find a $c$-convex $\psi$.

  • $\begingroup$ Hi James, and welcome to MO. Two things I don't get here - (1) Why it is obvious that $T$ and $d\pi$ look as you claim? (2) Can you clarify the supremum notations in the dual form? What are you taking a supremum over? $\endgroup$
    – Amir Sagiv
    Oct 18, 2019 at 21:37
  • $\begingroup$ Hi! I guess other transport plan or map would violate the cyclical monotonicity property, and would also necessarily have "crossing paths" in the transport plan. I've edited the question to better specify the supremum, but usually it's a well known sup in the optimal transport theory. $\endgroup$ Oct 18, 2019 at 21:54
  • $\begingroup$ that points are not in their Laguerre cell is not a problem, you can't assume they are in general $\endgroup$
    – alesia
    Oct 19, 2019 at 15:09
  • $\begingroup$ Indeed. I'm not troubled by the points not being contained within the Laguerre cells. What I don't understand is the inability to find a $\psi$ in this case that gives me the Laguerre cells $\endgroup$ Oct 20, 2019 at 8:53

1 Answer 1


Just like to share for anyone who ends up here - my problem was a lack of strict convexity in the cost function when represented as $c(x,y) = h(x-y)$. The function $h(x-y) = |x - y|$ is not strictly convex, so according to theory that can be found, for example in Gangbo and McCann, there is no guarantee of a unique transport solution and dual solution for which the usual $c$-transform relationship holds. Also, Vilanni's text proves existence and I missed the fact that there are no guarantees of uniqueness.


You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .