MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## Continuous Transportation Problem

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!

-

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.
 Thanks so much for your response, Tapio. This view of the marginalization is very helpful. Let me try to rephrase the heart of my question, which didn't come across well. Our goal is to prove optimality using duality, by proposing primal and dual feasible solutions with equal objective functions. So my question is this. I have a $\rho$ which I believe is optimal and I would like to prove this via weak duality. My problem is in showing that $\rho$ is primal feasible. How does one go about this? Is it possible with uncountably many constraints? (It's easy in the finite case.) – Carrie Nuttall Jul 6 2011 at 15:54