The Kantorovich formulation of optimal transport:
Let $\mu = \{\mu_1, \mu_2, \ldots, \mu_m\}$ and $\nu = \{\nu_1, \nu_2, \ldots, \nu_n\}$ be two probability measures, we aim to find a transport plan $\pi$ that minimizes the total transportation cost.
The discrete version of the optimal transport problem can be formulated as a linear programming problem. Here's the formulation:
\begin{align*}
\text{Minimize } & \sum_{i=1}^{m} \sum_{j=1}^{n} c(i, j) \pi(i, j) \\
\text{subject to } & \sum_{j=1}^{n} \pi(i, j) = \mu(i), \quad \forall i = 1, 2, \ldots, m \quad (\text{Marginal constraint 1}) \\
& \sum_{i=1}^{m} \pi(i, j) = \nu(j), \quad \forall j = 1, 2, \ldots, n \quad (\text{Marginal constraint 2}) \\
& \pi(i, j) \geq 0, \quad \forall i = 1, 2, \ldots, m \quad \text{and} \quad j = 1, 2, \ldots, n \quad (\text{Non-negativity constraint})
\end{align*}
In this formulation, $c(i, j)$ represents the cost of transporting one unit of mass from point $x_i$ in set $X$ to point $y_j$ in set $Y$. The variables $\pi(i, j)$ represent the amount of mass transported from $x_i$ to $y_j$.
Let $\pi^*$ be the optimal plan given $\mu$, $\nu$, and a certain cost matrix $C$ ($C$ is an $\mathbb{R}^{m \times n}$ matrix.
). And define the function $L$ to be such that L(C, $\mu$, $\nu$) = $\pi^*$.
My question is about the ijectivity of $L$, i.e If $L(C, \mu, \nu) = L(C', \mu, \nu)$, is $C = C'$ a necessary condition?
Best Answer
No. First, note that if you simply scale the cost function by some positive number $\lambda>0$, i.e. choose the cost $C'=\lambda \cdot C$, then the optimal solution stays the same.
Even if we exclude this "span of costs" $L$ is still not injective. To see this , note that for the special case of $\mu:=\frac{1}{N}\sum_{i=1}^N \delta_{x_i},\nu:=\frac{1}{N}\sum_{i=1}^N \delta_{y_i}$ for $x_i\neq x_j, y_i\neq y_j$ $(i\neq j)$ the optimal solution must be induced (i.e. $\pi=(\text{id},T)_\text{#} \mu$) by a map $$T: \lbrace x_1,\dots,x_N\rbrace\rightarrow\lbrace y_1,\dots,y_N\rbrace $$ since any solution $\pi$ must be a doubly-stochastic matrix, i.e. the rows sum to $1/N$ and the columns sum to $1/N$ and an optimal solution $\pi^*$ of a Linear Program always lies on the extramal points of the convex region, i.e. in this case the matrices with exactly one non-zero value in each row and each column. This set of matrices exactly corresponds to the bijections $T$ defined above.
This means that the image of $L(C,\mu,\nu)$ is finite (for the given $\mu,\nu$ above) and since there are infinitely many $C$ we can choose there must be an infinite set of costs $C'$ for which we have $L(C,\mu,\nu)=L(C',\mu,\nu)$.