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!



Continuous Transportation Problem
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.


