Suppose $\Omega$ is a suitably regular domain in $\mathbb{R}^n$ and $\rho\_0,\rho\_1\in\textrm{Prob}(\Omega)$. Benamou and Brenier showed that the $L\_2$ transportation distance between $\rho\_0$ and $\rho\_1$ can be computed as follows:


$$d(\rho\_0,\rho\_1)^2=\inf\_{\rho(x,t),v(x,t)}\int\_{\Omega}\int\_0^1\rho(x,t)|v(x,t)|^2\,dt\,dx$$


where $\rho(x,t)$ satisfies $\rho(x,0)=\rho\_0(x)$, $\rho(x,1)=\rho\_1(x)$, and $\frac{\partial\rho}{\partial t}+\nabla\cdot(\rho v)=0$. This formula appears in many discretizations of optimal transportation.


We know $d(\cdot,\cdot)$ satisfies the triangle inequality because it was derived from the Wasserstein distance. But, this evidence for the triangle inequality is "heavy" in that if you *define* Wasserstein distances using the above PDE formulation, you could only prove triangle inequality after showing a (complicated) relationship with the theory of optimal transportation.


**Is it possible to prove the triangle inequality directly from the "PDE-constrained optimization" formulation written above?** Even an informal proof that ignores regularity issues etc. would be useful for me.


Thanks!


PS -- The Benamou/Brenier paper is "A computational ﬂuid mechanics solution
to the Monge-Kantorovich mass transfer problem," which lives here: <http://link.springer.com/article/10.1007%2Fs002110050002>


PPS -- Also posted here, but I realized it's probably not the right place: <https://math.stackexchange.com/posts/796634/edit>



PDE-Based Triangle Inequality for Optimal Transportation
I first wrote a longer answer, but it got somehow lost. Here is a rewritten shorter one. The idea is to simply construct a curve going from $\rho\_0$ to $\rho\_1$ to $\rho\_2$. The only thing is to check how to make the reparametrization, i.e. decide the time $T$ when you move from the first transport to the other. This is how it should go:


Suppose $\rho\_0,\rho\_1,\rho\_2\in\textrm{Prob}(\Omega)$ with $d\_1 = d(\rho\_0,\rho\_1) >0$ and $d\_2 = d(\rho\_1,\rho\_2) >0$. Let $T \in (0,1)$ so that
$\frac{1-T}{T} = \frac{d\_1}{d\_2}$ and let $(\rho^1,v^1)$ and $(\rho^2,v^2)$ be admissible pairs (i.e. having the correct marginals and satisfying the continuity equation) for defining the infimum in the distances $d\_1$ and $d\_2$. Let us assume that they even realize the infima. Now define an admissible pair $(\rho,v)$ for the distance from $\rho\_0$ to $\rho\_2$ as
$$
\rho(x,t) = \begin{cases}
\rho^1(x,t/T), & t \le T\\
\rho^2(x,(t-T)/(1-T)), & t > T\\
\end{cases}
$$
and
$$
v(x,t) = \begin{cases}
\frac1Tv^1(x,t/T), & t \le T\\
\frac1{1-T}v^2(x,(t-T)/(1-T)), & t > T.\\
\end{cases}
$$
Now 
$$
d(\rho\_0,\rho\_2)^2\le \int\_{\Omega}\int\_0^1\rho(x,t)|v(x,t)|^2\,dt\,dx = \frac1{T}d\_1^2 + \frac1{1-T}d\_2^2 = (d\_1 + d\_2)^2.
$$


