Continuous Transportation Problem

Question

Hi all, I'm trying to formulate an infinite linear program to prove optimality (via duality) for the Continuous Transportation Problem, e.g. the Kantorovich-Wasserstein distance. This is the continuous version of the discrete transformation of the Transportation Problem commonly solved by the transportation simplex algorithm.

To be concrete, say we are given weighted point sets $(A,p)$ and $(B,q)$, where $A=\{a_1,\dots,a_{|A|}\}$ is a finite subset of the metric space $(\Omega,d_\Omega)$; $p=(p_1,\dots,p_{|A|})$ is a vector of associated nonnegative weights summing to one, and similar definitions hold for $B$ and $q$.

The optimal transportation distance ($d_{KW}$) between $(A,p)$ and $(B,q)$ is defined by the minimization of: \begin{align} \sum_{i=1}^{|A|} \sum_{j=1}^{|B|} f_{ij}d_\Omega(a_i,b_j) \end{align}

where the optimal flow $F^*=f_{ij}^*$ between $(A,p)$ and $(B,q)$ is the solution of the linear program \begin{align} \begin{array}{rcllr} f_{ij} &\geq& 0, & 1 \leq i \leq |A|, 1 \leq j \leq |B|\\ \sum_{j=1}^{|B|} f_{ij} &=& p_i, & 1 \leq i \leq |A| &\textrm{(1)}\\ \sum_{i=1}^{|A|} f_{ij} &=& q_j, & 1 \leq j \leq |B| &\textrm{(2)}\\ \end{array} \end{align}

According to Anderson and Philpott (http://www.jstor.org/pss/3689247), this can be generalized to the infinite case as follows:

For continuous functions $f_1$ on $X$ and $f_2$ on $Y$, define $\hat f_1$ and $\hat f_2$ on $X\times Y$ by \begin{align} \hat f_1(x,y)=f_1(x) & \textrm{ for all }x\in X, y\in Y\\ \hat f_2(x,y)=f_2(y) & \textrm{ for all }x\in X, y\in Y.\\ \end{align}

We now minimize \begin{align} \int_{X\times Y} c(x,y)d\rho (x,y) \end{align} Subject to: \begin{align} \begin{array}{rcllr} \int_{X\times Y} \hat f_1(x,y) d\rho (x,y) &=& \int_X f_1(x) d\mu_1(x) &\textrm{(3)}\\ &&\text{for all continuous functions $f_1$ on $X$}\\ \int_{X\times Y} \hat f_2(x,y) d\rho (x,y) &=& \int_Y f_2(y) d\mu_2(x) &\textrm{(4)}\\ && \text{for all continuous functions $f_2$ on $Y$}\\ \rho \geq 0\\ \end{array} \end{align}

Here $\rho$, $\mu_1$ and $\mu_2$ are nonnegative Radon measures and $c$ is a continuous function. $X$ and $Y$ are compact spaces with $\mu_1(X)=\mu_2(Y)$.

So, my question is: according to Anderson and Philpott, constraints (1) and (3) & constraints (2) and (4) are capturing the same conditions.

How is this possible? Constraints (1) and (2) limit the amount of masses shipped or received (respectively) by each point. How is this reflected in constraints (3) and (4)? What is the significance of functions $f_1$ and $f_2$? I would expect constraints (3) and (4) would be:

\begin{align} \begin{array}{rcll} \int_{x\in X} f_{X\times Y}(x,y) dx &=& f_{Py}(y) &y\in Y\\ \int_{y\in Y} f_{X\times Y}(x,y) dy &=& f_{Px}(x) &x\in X\\ \end{array} \end{align}

where the $f_P$'s correspond to pdfs, e.g., if X and Y are probability distributions. (In other words, they capture the marginalization constraints.)

What am I missing? Thanks!

Answer 1

If I understand your confusion correctly, you are trying to relate $f_1$ to $p_i$ and $f_2$ to $p_2$. Those are not related. The measure $\rho$ corresponds to $\{f_{ij}\}_{ij}$, the measure $\mu_1$ to $\{p_i\}_i$ and $\mu_2$ to $\{q_j\}_j$. The functions $f_1$ and $f_2$ are used as test functions to say that $\mu_1$ is the first marginal of $\rho$, and $\mu_2$ is the second. You could also write (3) as $$\mu_1(A) = \rho(A \times Y) \qquad\text{for all } A$$ and (4) correspondingly. I hope this helps.

Answer 2

Regarding your question below the answer of Tapio Rajala: Testing feasibility of $\rho$ simply amounts to checking that $$\mu_1(A) = \rho(A\times Y),\qquad\text{and}\qquad \mu_2(B) = \rho(X\times B)$$ but probably your problem is, that you have to do this for all sets $A$ and $B$. Alternatively, you could check the integrals (3) and (4) for all continuous functions.

In the finite dimensional case your "measure space" has atoms, i.e. your sets $A$ and $B$ (sorry for the overload) have subsets with minimal mass (i.e. that one-element subsets) and hence, you can show what you want for the atoms and that's it. In the infinite dimensional case you need to work with all subsets since there are in general no atoms on which you can build. I think it should work if you check the measures for enough simple sets as all rectangles (which is a good point to start anyway since it will provide you with a feeling what is going on).

In case you did not know already: The duality in the continuous case is also nicely explained in Villani's book "Optimal Transport - old and New", Chapter 5.