Kantorovich duality theorem

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.