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.

A function assigning energy to the separation of two particles. The common symmetric case is an even function, $W(z)=W(-z)$. Its average over pairs defines an interaction energy. If the Hessian matrix is bounded, the gradient is globally Lipschitz and grows at most linearly; its convolution with a probability measure therefore needs only a finite first absolute moment, even though the potential itself can require a second absolute moment.

For a twice continuously differentiable interaction potential with $\Vert D^{2}W\Vert \le L$ and a probability measure with finite first absolute moment, this subtraction produces a finite potential even if $W\ast \mu$ is infinite. Taylor's formula and linear growth of the gradient giveDominated differentiation under the integral sign gives $\nabla V_{\mathrm{ren}}=(\nabla W)\ast \mu$ and $D^2{V}_{\mathrm{ren}}=(D^{2}W)\ast \mu$. If the unrenormalized convolution is finite, the two potentials differ only by a constant, so they generate the same velocity field when that field depends on their gradient.

The factor $1/2$ counts unordered pairs once. For a symmetric interaction potential, this energy is unchanged by translating the entire probability measure. It therefore cannot have positive uniform displacement convexity on the unrestricted space containing translations. If $D^{2}W\ge \lambda I$, integrate the pointwise strong convexity inequality along an optimal transport plan and its independent copy. The variance identity for independent copies then gives $\lambda$-displacement convexity on every class with fixed barycenter of a measure, whenever the integrals are finite.

A function describing the energy of placing a particle at a position in a fixed external field. Its associated confinement energy is linear in the probability measure representing the particle distribution. A common example is $V(x)=|x{|}^2/2$.

The average of a confinement potential against a probability measure. A potential bounded below with at most quadratic growth has finite energy on probability measures with finite second absolute moments. A lower Hessian matrix bound $D^{2}V\ge \lambda I$ gives $\lambda$-displacement convexity: apply convexity of $V-\lambda |\cdot {|}^2/2$ along each particle segment in an optimal transport plan, then integrate. Quadratic growth of $V$ alone does not justify two differentiations under the energy integral.

A set of source-destination pairs has this property if every finite cyclic reassignment of destinations cannot lower its total cost. A transport plan has the property if it is concentrated on such a set. For a general cost, this is stronger than a two-point monotonicity test.

An optimal transport plan of finite cost for a finite continuous cost function is c-cyclically monotone. A strict violation at finitely many support points persists in small product neighborhoods; subtracting small normalized pieces and inserting cyclically re-paired product measures preserves both marginals and strictly improves the finite cost. The finite-value hypothesis matters: if every competitor has infinite cost, a nonmonotone plan may still be an extended-value minimizer.

A transport plan is strongly c-monotone if Borel Kantorovich potentials satisfy the displayed feasible inequality everywhere and equality almost everywhere for the plan. Extended values $-\infty$ away from the full marginal-measure sets may be permitted. This is a potential certificate, not a strict version of every cyclic inequality. A finite continuous cost allows the transport potential path construction.

For a nonnegative cost, simultaneous symmetric clipping preserves feasibility of a pair of Kantorovich potentials. On their equality set the clipped sums are nonnegative and increase to the cost. Their bounded integrals are fixed by the marginals, so monotone convergence theorem proves optimality without subtracting undefined infinite marginal integrals.

Anchor a countable dense subset of a closed c-cyclically monotone support. Take the infimum of accumulated differences $c(x_{j+1},y_j)-c(x_j,y_j)$ along chains ending at a variable point. Cyclical monotonicity bounds this potential below on the support projection. Its cost transform gives the other potential, with equality on the support. Continuity makes both potentials upper semicontinuous and thus Borel.

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 atomless source and target probabilities with continuous strictly increasing cumulative distributions, the squared-distance optimal coupling is unique. Two-point optimality forbids crossed support pairs. This makes every pair of source and target lower-tail events nested up to null sets and forces the displayed joint distribution, which is the common-quantile coupling and is induced by $G^{-1}F$.

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.

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.

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$.

When source and target have continuous strictly increasing cumulative distributions, all transport maps are obtained by choosing a Lebesgue-measure-preserving map $S$ on the unit interval. The maps $F$ and $G$ turn the two measures into uniform measure. The choice $S=\mathrm{id}$ gives the monotone rearrangement.