Continuous Transportation Problem

2011-07-05T22:52:23Z

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 by Tapio Rajala for Continuous Transportation Problem

2011-07-06T05:47:47Z

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.

Continuous Transportation Problem - MathOverflow

Continuous Transportation Problem

Answer by Tapio Rajala for Continuous Transportation Problem