# A problem with the dual form of semi-discrete optimal transport

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

• 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? – Amir Sagiv Oct 18 '19 at 21:37
• 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. – James Nichols Oct 18 '19 at 21:54
• that points are not in their Laguerre cell is not a problem, you can't assume they are in general – alesia Oct 19 '19 at 15:09
• 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 – James Nichols Oct 20 '19 at 8:53

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.