Optimal transport

Optimal transport minimizes the cost of moving one probability measure to another. The Monge optimal transport problem uses a transport map; the Kantorovich optimal transport problem allows a transport plan that can split mass.

For an atomless measure $\mu$ on $\mathbb{R}$ with cumulative distribution function $F$, the monotone transport to a target with quantile function $G^{-1}$ is $T=G^{-1}\circ F$, defined $\mu$-almost everywhere. It minimizes well-defined costs $d(x-y)$ for convex continuous $d$. With atoms in the source, the common-quantile transport plan $(F^{-1},G^{-1}{)}_{\#}\mathcal{U}(0,1)$ remains available but need not be induced by a map.

For probability measures on ${\mathbb{R}}^d$ with finite second moments, a transport plan minimizes the quadratic cost exactly when it is concentrated on the graph of the subdifferential of a sequentially lower semicontinuous proper convex function.

For probability measures on ${\mathbb{R}}^d$ with finite second moments and a source satisfying absolute continuity of measures with respect to Lebesgue measure, the quadratic Kantorovich optimal transport problem has a unique optimal transport plan. It is induced by the gradient of a convex function, which also uniquely solves the Monge optimal transport problem up to a source-null set.

The Kantorovich problem minimizes $\int c(x,y)d\pi (x,y)$ over transport plans $\pi$ with marginal distributions $\mu ,\nu$. It relaxes the Monge optimal transport problem by allowing source mass to split among destinations.

For probability measures defined as Borel measures on Polish spaces and a nonnegative sequentially lower semicontinuous cost, the minimum cost over transport plans equals the supremum of $\int ud\mu +\int vd\nu$ over integrable Kantorovich potentials satisfying $u(x)+v(y)\le c(x,y)$. The primal minimum is attained; a dual maximum needs additional assumptions. Compact metric spaces and a finite continuous cost suffice for attainment of both extrema.

Kantorovich potentials are the functions in the dual of the Kantorovich optimal transport problem. A feasible pair satisfies $u(x)+v(y)\le c(x,y)$ and provides a lower bound $\int ud\mu +\int vd\nu$ for every transport plan. An optimal pair attaining the dual value provides an optimality certificate.

A transport plan is a coupling of probability distributions $\mu ,\nu$, that is, a probability measure on the product space with those marginal distributions. Unlike a transport map, it need not be concentrated on the graph of a function.

Given a cost $c$ and probability measures $\mu ,\nu$, the Monge problem minimizes $\int c(x,T(x))d\mu (x)$ over measurable transport maps with pushforward measure $T_{\#}\mu =\nu$. The feasible set may be empty because a map cannot split an atom of a measure.

A transport map from $\mu$ to $\nu$ is a measurable function $T$ satisfying $T_{\#}\mu =\nu$. Its graph defines the transport plan $(\mathrm{Id},T{)}_{\#}\mu$.