Optimal Transport Problem

In mathematics and economics, transportation theory or transport theory is a name given to the study of optimal transportation and allocation of resources. The problem was formalized by the French mathematician Gaspard Monge in 1781.G. Monge. ''Mémoire sur la théorie des déblais et des remblais. Histoire de l’Académie Royale des Sciences de Paris, avec les Mémoires de Mathématique et de Physique pour la même année'', pages 666–704, 1781.

In the 1920s A.N. Tolstoi was one of the first to study the transportation problem mathematically. In 1930, in the collection ''Transportation Planning Volume I'' for the National Commissariat of Transportation of the Soviet Union, he published a paper "Methods of Finding the Minimal Kilometrage in Cargo-transportation in space".

Major advances were made in the field during World War II by the Soviet mathematician and economist Leonid Kantorovich.L. Kantorovich. ''On the translocation of masses.'' C.R. (Doklady) Acad. Sci. URSS (N.S.), 37:199–201, 1942. Consequently, the problem as it is stated is sometimes known as the Monge–Kantorovich transportation problem. The linear programming formulation of the transportation problem is also known as the Hitchcock–Koopmans, i.e., if the cumulative distribution function $F_\mu = \mathbf\rightarrow[0,1]$ of $\mu$ is a continuous function, then $F_^ \circ F_ : \mathbf \to \mathbf$ is an optimal transport map. It is the unique optimal transport map if $h$ is strictly convex.
# We have
::$\min_ \int_ c(x, y) \, \mathrm \gamma (x, y) = \int_0^1 c \left( F_^ (s), F_^ (s) \right) \, \mathrm s.$

The proof of this solution appears in Rachev & Rüschendorf (1998).Rachev, Svetlozar T., and Ludger Rüschendorf. ''Mass Transportation Problems: Volume I: Theory''. Vol. 1. Springer, 1998.

Discrete version and linear programming formulation

In the case where the margins $\mu$ and $\nu$ are discrete, let $\mu_x$
and $\nu_y$ be the probability masses respectively assigned to $x\in \mathbf$ and $y\in \mathbf$, and let $\gamma _$ be the probability of an $xy$ assignment. The objective function in the primal Kantorovich problem is then

: $\sum_ \gamma_c_$

and the constraint $\gamma \in \Gamma \left( \mu ,\nu \right)$ expresses as

: $\sum_\gamma_=\mu_x,\forall x\in \mathbf$
and
: $\sum_ \gamma_=\nu_y,\forall y\in \mathbf.$

In order to input this in a linear programming problem, we need to vectorize the matrix $\gamma_$ by either stacking its columns or its rows, we call $\operatorname$ this operation. In the column-major order, the constraints above rewrite as

: $\left( 1_\otimes I_\right) \operatorname\left( \gamma \right) =\mu$ and $\left( I_\otimes 1_\right) \operatorname\left( \gamma \right) =\nu$

where $\otimes$ is the Kronecker product, $1_$ is a matrix of size $n\times m$ with all entries of ones, and $I_$ is the identity matrix of size $n$. As a result, setting $z=\operatorname\left( \gamma \right)$, the linear programming formulation of the problem is

:
\begin
& \text \operatorname(c)^\top z \\ pt& \text \\ pt& z \ge 0 \\ pt& \begin
1_\otimes I_ \\
I_\otimes 1_
\end \\ pt& z=\binom
\end

which can be readily inputted in a large-scale linear programming solver (see chapter 3.4 of Galichon (2016) Galichon, Alfred. ''Optimal Transport Methods in Economics''. Princeton University Press, 2016.).

Semi-discrete case

In the semi-discrete case, $X=Y=\mathbf^d$ and $\mu$ is a continuous distribution over $\mathbf^d$, while $\nu =\sum_^\nu _\delta_$ is a discrete distribution which assigns probability mass $\nu _$ to site $y_j \in \mathbf^d$. In this case, we can see that the primal and dual Kantorovich problems respectively boil down to:
$\inf \left\$
for the primal, where $\gamma \in \Gamma \left( \mu ,\nu \right)$ means that $\int_ d\gamma _\left( x\right) =\nu _$ and $\sum_d\gamma_\left( x\right) =d\mu \left( x\right)$, and:
$\sup \left\$
for the dual, which can be rewritten as:
$\sup_\left\$
which is a finite-dimensional convex optimization problem that can be solved by standard techniques, such as gradient descent.

In the case when $c\left( x,y\right) =\left\vert x-y\right\vert ^/2$, one can show that the set of $x\in \mathbf$ assigned to a particular site $j$ is a convex polyhedron. The resulting configuration is called a power diagram.

Quadratic normal case

Assume the particular case $\mu =\mathcal\left( 0,\Sigma_X\right)$, $\nu =\mathcal \left( 0,\Sigma _\right)$, and $c(x,y) =\left\vert y-Ax\right\vert^2/2$ where $A$ is invertible. One then has

: $\varphi(x) =-x^\top \Sigma_X^\left( \Sigma_X^A^\top \Sigma_Y A\Sigma_X^\right) ^\Sigma_^x/2$

: $\psi(y) =-y^\top A\Sigma_X^\left( \Sigma_X^A^\top \Sigma_Y A\Sigma_^\right)^ \Sigma_X^Ay/2$

: $T(x) = (A^\top)^\Sigma_X^ \left(\Sigma_X^A^\top \Sigma_Y A\Sigma_X^ \right)^ \Sigma_X^$

The proof of this solution appears in Galichon (2016).

Separable Hilbert spaces

Let $X$ be a separable Hilbert space. Let $\mathcal_p(X)$ denote the collection of probability measures on $X$ that have finite $p$-th moment; let $\mathcal_p^r(X)$ denote those elements $\mu \in \mathcal_p(X)$ that are Gaussian regular: if $g$ is any strictly positive Gaussian measure on $X$ and $g(N) = 0$, then $\mu(N) = 0$ also.

Let $\mu \in \mathcal_p^r (X)$, $\nu \in \mathcal_p(X)$, $c (x, y) = , x - y , ^p/p$ for $p\in(1,\infty), p^ + q^ = 1$. Then the Kantorovich problem has a unique solution $\kappa$, and this solution is induced by an optimal transport map: i.e., there exists a Borel map $r\in L^p(X, \mu; X)$ such that

:$\kappa = (\mathrm_X \times r)_ (\mu) \in \Gamma (\mu, \nu).$

Moreover, if $\nu$ has bounded support, then

:$r(x) = x - , \nabla \varphi (x) , ^ \, \nabla \varphi (x)$

for $\mu$-almost all $x\in X$ for some locally Lipschitz, ''c''-concave and maximal Kantorovich potential $\varphi$. (Here $\nabla \varphi$ denotes the Gateaux derivative of $\varphi$.)

Entropic regularization

Consider a variant of the discrete problem above, where we have added an entropic regularization term to the objective function of the primal problem

:
\begin
& \text \sum_\gamma_c_+\varepsilon \gamma_ \ln \gamma_ \\ pt& \text \\ pt& \gamma\ge0 \\ pt& \sum_\gamma _ =\mu _,\forall x\in \mathbf \\ pt& \sum_\gamma_ = \nu_y, \forall y\in \mathbf
\end

One can show that the dual regularized problem is

:$\max_ \sum_ \varphi_x \mu_x + \sum_ \psi_y v_y - \varepsilon \sum_ \exp \left( \frac\right)$

where, compared with the unregularized version, the "hard" constraint in the former dual ($\varphi_x + \psi_y - c_\geq 0$) has been replaced by a "soft" penalization of that constraint (the sum of the $\varepsilon \exp \left( (\varphi _x + \psi_y - c_)/\varepsilon \right)$ terms ). The optimality conditions in the dual problem can be expressed as

: $\mu_x = \sum_ \exp \left( \frac \right) ~\forall x\in \mathbf$

: $\nu_y = \sum_ \exp \left( \frac\right) ~\forall y\in \mathbf$

Denoting $A$ as the $\left\vert \mathbf\right\vert \times \left\vert \mathbf\right\vert$ matrix of term $A_=\exp \left(-c_ / \varepsilon \right)$, solving the dual is therefore equivalent to looking for two diagonal positive matrices $D_$ and $D_$ of respective sizes $\left\vert \mathbf\right\vert$ and $\left\vert \mathbf\right\vert$, such that $D_AD_1_=\mu$ and $\left( D_AD_\right) ^1_=\nu$. The existence of such matrices generalizes Sinkhorn's theorem and the matrices can be computed using the Sinkhorn–Knopp algorithm, which simply consists of iteratively looking for $\varphi _$ to solve , and $\psi _$ to solve . Sinkhorn–Knopp's algorithm is therefore a coordinate descent algorithm on the dual regularized problem.

Applications

The Monge–Kantorovich optimal transport has found applications in wide range in different fields. Among them are:
* Image registration and warping
* Reflector design
* Retrieving information from shadowgraphy and proton radiography
* Seismic tomography and reflection seismology
* The broad class of economic modelling that involves gross substitutes property (among others, models of matching and discrete choice).

See also

* Wasserstein metric
* Transport function
* Hungarian algorithm
* Transportation planning
* Earth mover's distance
* Monge–Ampère equation

References

Further reading

*

{{DEFAULTSORT:Transportation Theory
Calculus of variations
Matching (graph theory)
Mathematical economics
Measure theory
Transport economics
Optimization in vector spaces
Mathematical optimization in business