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.

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.