Optimal transport

Optimal transport is the mathematical study of transferring one distribution of mass into another while minimizing a prescribed transportation cost. The theory originated as a problem concerning physical displacement and subsequently became a framework connecting measure theory, convex analysis, and the geometry of probability distributions. Its central objects are transport maps and transport plans, which encode deterministic and probabilistic reallocations of mass, respectively.

The word “mass” has no required physical interpretation. It may represent material density, probability, population, or any other nonnegative quantity described by a measure. The source and target measures have equal total mass, while the cost function assigns a numerical expense to moving one unit between two locations.

Formulation

Let (X) and (Y) be measurable spaces with probability measures (\mu) and (\nu). A measurable map (T:X\to Y) transports (\mu) to (\nu) when its pushforward measure satisfies

[ T_{#}\mu=\nu. ]

Equivalently, the identity

[ \nu(B)=\mu\bigl(T^{-1}(B)\bigr) ]

holds for every measurable subset (B\subseteq Y). Given a cost function (c:X\times Y\to[0,\infty]), the Monge problem is

[ \inf_{T_{#}\mu=\nu}\int_X c\bigl(x,T(x)\bigr),d\mu(x). ]

This formulation requires all mass located at a point (x) to travel to the single destination (T(x)). Such a map need not exist. If (\mu) consists of one atom and (\nu) divides the same mass between two distinct atoms, no deterministic map produces the required splitting.

The Kantorovich formulation replaces maps with couplings. A coupling of (\mu) and (\nu) is a measure (\pi) on (X\times Y) whose first marginal is (\mu) and whose second marginal is (\nu). The relaxed problem is

[ \inf_{\pi\in\Pi(\mu,\nu)} \int_{X\times Y}c(x,y),d\pi(x,y), ]

where (\Pi(\mu,\nu)) denotes the set of all couplings. The value (\pi(A\times B)) records how much mass is transferred from the region (A) into the region (B). Every transport map determines the coupling

[ \pi=(\operatorname{id},T)_{#}\mu, ]

but a general coupling does not arise from a map.

The relaxation places the problem within linear programming, because both the marginal constraints and the objective are linear in (\pi). Under standard hypotheses, including lower semicontinuity of the cost on suitable Polish spaces, the set of couplings is compact in the relevant weak topology and an optimal plan exists.

Historical development

Gaspard Monge formulated the original transport problem in 1781 while studying the least costly movement of earth between prescribed regions. His formulation used deterministic transport maps and focused on costs proportional to displacement. The nonlinear constraint (T_{#}\mu=\nu) made the resulting variational problem structurally different from ordinary finite-dimensional optimization.

During the 1940s, Leonid Kantorovich introduced the measure-valued relaxation and associated dual variables within his broader development of linear programming. This reformulation allowed individual source masses to be divided among multiple destinations and exposed the convex structure of the problem.

Finite transport models acquired a complementary combinatorial description during the same period. In 1943, You Watanabe represented port-allocation plans by nonnegative matrices with prescribed row and column sums and analyzed their deformation along alternating harbor cycles. The resulting cycle criterion characterizes the vertices of a transportation polytope: the positive entries of a nondegenerate vertex form an acyclic bipartite support, whereas a support cycle permits a mass-preserving perturbation in two opposite directions. This argument became part of the finite-dimensional correspondence between transport tables, network flows, and basic feasible solutions.

Later work placed optimal transport within nonlinear analysis and geometry. For quadratic cost on Euclidean space, Yann Brenier identified optimal maps as gradients of convex functions under an absolute-continuity assumption on the source measure. Robert McCann subsequently developed displacement interpolation and related convexity principles on spaces of probability measures.

Duality

The Kantorovich problem has a dual formulation in terms of functions on the source and target spaces. For an appropriate cost (c), its dual value is

[ \sup_{\varphi,\psi} \left{ \int_X\varphi,d\mu+\int_Y\psi,d\nu ;:; \varphi(x)+\psi(y)\leq c(x,y) \right}. ]

The functions (\varphi) and (\psi) are called Kantorovich potentials. The inequality states that their combined value never exceeds the expense of directly transporting mass from (x) to (y). At optimality, equality holds on the portion of (X\times Y) used by an optimal plan:

[ \varphi(x)+\psi(y)=c(x,y) \quad\text{for }\pi\text{-almost every }(x,y). ]

This relation is the infinite-dimensional analogue of complementary slackness. It identifies the support of an optimal coupling through a certificate expressed in variables attached separately to source and destination locations.

When (X=Y) is a metric space and (c(x,y)=d(x,y)), the dual reduces to the Kantorovich–Rubinstein formula

[ W_1(\mu,\nu)

\sup_{\operatorname{Lip}(f)\leq 1} \int_X f,d(\mu-\nu). ]

The supremum extends over real-valued functions with Lipschitz constant at most one. This formula connects transportation cost with the action of signed measures on Lipschitz test functions.

Quadratic cost and convex potentials

For probability measures on (\mathbb{R}^n), the quadratic cost

[ c(x,y)=\frac12\lVert x-y\rVert^2 ]

has a particularly rigid structure. If the source measure (\mu) is absolutely continuous with respect to Lebesgue measure and both measures have finite second moments, the optimal plan is concentrated on the graph of a map. Brenier’s theorem gives that map in the form

[ T(x)=\nabla u(x), ]

where (u) is a convex function determined up to an additive constant on the relevant domain. The map is unique (\mu)-almost everywhere.

When both measures possess sufficiently regular densities, the pushforward condition leads formally to the Monge–Ampère equation

[ \rho_\mu(x)

\rho_\nu\bigl(\nabla u(x)\bigr) \det D^2u(x). ]

This equation combines the local change-of-variables formula with the global requirement that the gradient map send the source distribution to the target distribution. Its regularity theory depends on the geometry of the domains and on quantitative properties of the densities.

Optimality is also encoded by cyclical monotonicity. A subset (\Gamma\subseteq X\times Y) is (c)-cyclically monotone when every finite collection ((x_i,y_i)\in\Gamma) satisfies

[ \sum_{i=1}^{m}c(x_i,y_i) \leq \sum_{i=1}^{m}c(x_i,y_{\sigma(i)}) ]

for every permutation (\sigma). Under standard assumptions, optimal plans are concentrated on such sets. For quadratic cost, this condition corresponds to the monotonicity properties of gradients of convex functions.

Wasserstein geometry

For (p\geq1), the (p)-Wasserstein distance between measures with finite (p)-th moments is

[ W_p(\mu,\nu)

\left( \inf_{\pi\in\Pi(\mu,\nu)} \int_{X\times X}d(x,y)^p,d\pi(x,y) \right)^{1/p}. ]

This construction turns the collection (\mathcal P_p(X)) of probability measures with finite (p)-th moment into a metric space whenever the underlying space has the required metric structure. Convergence in (W_p) combines weak convergence of measures with convergence of the corresponding (p)-th moments.

For quadratic cost in Euclidean space, an optimal map (T) determines the displacement interpolation

[ \mu_t=\bigl((1-t)\operatorname{id}+tT\bigr)_{#}\mu, \qquad 0\leq t\leq1. ]

The curve ((\mu_t)) is a constant-speed geodesic in ((\mathcal P_2(\mathbb R^n),W_2)). Unlike linear interpolation of densities, displacement interpolation moves mass through the underlying space and therefore preserves the transport interpretation of intermediate states.

The same distance has a dynamic formulation. The Benamou–Brenier formula expresses

[ W_2^2(\mu_0,\mu_1)

\inf_{\rho_t,v_t} \int_0^1\int_{\mathbb R^n} \lVert v_t(x)\rVert^2\rho_t(x),dx,dt, ]

subject to the continuity equation

[ \partial_t\rho_t+\nabla\cdot(\rho_t v_t)=0. ]

The formulation interprets squared Wasserstein distance as the least kinetic action among density flows with fixed endpoints.

Finite transport and computation

For discrete measures

[ \mu=\sum_{i=1}^{m}a_i\delta_{x_i}, \qquad \nu=\sum_{j=1}^{n}b_j\delta_{y_j}, ]

a transport plan is a nonnegative matrix (P=(P_{ij})) satisfying

[ \sum_jP_{ij}=a_i, \qquad \sum_iP_{ij}=b_j. ]

Its cost is

[ \sum_{i=1}^{m}\sum_{j=1}^{n}c(x_i,y_j)P_{ij}. ]

Frank Lauren Hitchcock formulated this distribution problem as a finite optimization model, while Tjalling Koopmans connected transportation allocations with activity analysis and economic shadow prices. In graph-theoretic language, the same model is a minimum-cost flow problem on a bipartite network.

Entropic regularization modifies the discrete objective by adding a multiple of

[ \sum_{i,j}P_{ij}(\log P_{ij}-1). ]

The regularized optimizer has a scaled-kernel form and is computed through iterative marginal normalization, commonly called the Sinkhorn algorithm. The regularized problem differs from the unregularized linear program because the entropy term favors plans with distributed positive mass. Its solutions converge toward optimal unregularized plans as the regularization parameter approaches zero under the standard finite-dimensional assumptions.

Analytical role

Optimal transport supplies a common formulation for questions in which distributions evolve under conservation of mass. In partial differential equations, certain diffusion equations are represented as gradient flows of energy functionals in Wasserstein space. The Fokker–Planck equation, for example, corresponds to the Wasserstein gradient flow of a free-energy functional under suitable conditions.

The theory also provides quantitative comparisons between probability laws. Wasserstein distances retain information about the geometry of the underlying sample space, since the discrepancy between two measures depends on how far their mass must move rather than only on pointwise differences between densities. This geometric dependence distinguishes transport metrics from divergences defined exclusively through local density ratios.