Kantorovich optimal transport problem

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.

The transport cost function assigns a cost to a unit of mass moved from $x$ to $y$. A transport plan has total cost $\int cd\pi$. Costs separating as $a(x)+b(y)$ have the same well-defined total for every coupling of fixed marginals.

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.

For compact metric spaces and a continuous cost, define the marginal functional $\ell (f(x)+g(y))=\int fdP+\int gdQ$. Its majorant envelope $p(h)={\inf }_{s\ge h}\ell (s)$ is finite and sublinear. The dual value is $-p(-c)$. Assign that value to the cost direction and use the dominated Hahn-Banach theorem to obtain a positive linear functional on all continuous functions of two variables. The Riesz-Markov-Kakutani representation theorem turns it into an optimal transport plan with the prescribed marginals.

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.