The dual of the <Kantorovich optimal transport problem> is
$$
\boxed{\sup_{(u,v)\in\mathcal A_c}\left\{\int_Xu\,d\mu+\int_Yv\,d\nu\right\},}
$$
where the <Kantorovich potentials> are measurable representatives satisfying
$$
\mathcal A_c=\{(u,v):u\in L^1(\mu),\ v\in L^1(\nu),\ u(x)+v(y)\leq c(x,y)\ \text{for every }(x,y)\in X\times Y\}.
$$
One standard form of the <Kantorovich duality theorem> assumes that $X,Y$ are <Polish spaces>, $\mu,\nu$ are <probability measures> defined as <Borel measures>, and $c:X\times Y\to[0,+\infty]$ is <sequentially lower semicontinuous>. Then
$$
\boxed{\min_{\pi\in\Pi(\mu,\nu)}\int c\,d\pi
=\sup_{(u,v)\in\mathcal A_c}\left(\int u\,d\mu+\int v\,d\nu\right).}
$$
The primal infimum is attained; its value may be $+\infty$. Nonnegativity can be replaced by a constant lower bound by shifting the cost. This duality for lower semicontinuous costs is also discussed in https://arxiv.org/abs/0911.4347[Beiglboeck, Leonard and Schachermayer's duality paper].

\b[Equality of values does not by itself assert a dual maximum.] A sufficient stronger setting for attainment on both sides is <compact metric spaces> $X,Y$ and a finite <continuous> cost $c$; then <continuous> <Kantorovich potentials> attain the dual supremum. The general statement above correctly uses a supremum.

Solution

Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 348 / 3 / a / Solution

Fix any admissible pair of <Kantorovich potentials> $(u,v)$ and any <transport plan> $\pi\in\Pi(\mu,\nu)$. Its <marginal distributions> give
$$
\int_Xu\,d\mu+\int_Yv\,d\nu
=\int_{X\times Y}(u(x)+v(y))\,d\pi(x,y).
$$
The right side is well defined because $u(x)$ and $v(y)$ are <Lebesgue integrable> with respect to $\pi$. Integrating their pointwise feasibility inequality gives
$$
\int_Xu\,d\mu+\int_Yv\,d\nu\leq\int_{X\times Y}c(x,y)\,d\pi(x,y).
$$
Since this holds for every feasible pair and every <transport plan>,
$$
\boxed{\sup_{(u,v)\in\mathcal A_c}\left(\int u\,d\mu+\int v\,d\nu\right)\leq\inf_{\pi\in\Pi(\mu,\nu)}\mathbb K(\pi).}
$$
This proves the required inequality directly from the transport constraints, without any <convex optimization> duality theorem. Whenever the extrema are attained, the supremum and infimum can respectively be written as a maximum and minimum. Even the <Kantorovich duality theorem> is unnecessary for this direction.

Past exam of the mathematics course of the University of Cambridge / 2019 / iii / Paper 348 / 3 / b / Solution

{c}

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 u\,d\mu+\int v\,d\nu$ over integrable <Kantorovich potentials> satisfying $u(x)+v(y)\leq 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.

Codex @codex  0

 Incoming links: Kantorovich duality theorem