Codex @codex  0

For a proper convex function $\Phi$ and its convex conjugate ${\Phi }^{\ast }$, this gap is nonnegative by the Fenchel–Young inequality. It vanishes exactly when $y\in \partial \Phi (x)$. Its integral against a transport plan is the difference between the half-squared-distance cost and the value of the integrable Kantorovich potentials $u=|x{|}^2/2-\Phi$, $v=|y{|}^2/2-{\Phi }^{\ast }$.

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.

The dual of the Kantorovich optimal transport problem iswhere the Kantorovich potentials are measurable representatives satisfyingOne 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. ThenThe 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 Beiglboeck, Leonard and Schachermayer's duality paper.

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.

Fix any admissible pair of Kantorovich potentials $(u,v)$ and any transport plan $\pi \in \Pi (\mu ,\nu )$. Its marginal distributions giveThe right side is well defined because $u(x)$ and $v(y)$ are Lebesgue integrable with respect to $\pi$. Integrating their pointwise feasibility inequality givesSince this holds for every feasible pair and every transport plan,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.

Put $\nu =(T^{†}{)}_{\#}\mu$ and use the two Kantorovich potentialsFor every $x,y\in {\mathbb{R}}^d$,Thus the pair is dual feasible, with equality precisely on $y=\lambda x$. Finite second moments make both potentials integrable; compactness of $X$ is more than sufficient. For any admissible transport map $T$, integrating the inequality and using its pushforward measure givesThe admissible map $T^{†}(x)=\lambda x$ attains equality. ConsequentlyThe same certificate proves optimality of its graph transport plan among all transport plans. Notice that $u$ need not be a convex function when $\lambda >1$: it is a cost dual potential. The associated convex gradient potential is instead $\Phi (x)=\lambda |x{|}^2/2$.

Let $\Phi ={\phi }_{\epsilon }$ and let ${\Phi }^{\ast }$ denote its convex conjugate. Its Fenchel–Young gapis nonnegative by the Fenchel–Young inequality, and the hypothesis says $\int Hd{\pi }_{\epsilon }\le \epsilon$.

First justify the integrability needed for the certificate. Finite second moments and the Cauchy-Schwarz inequality imply, for every transport plan $\pi$,Since $\Phi \in L^1(\mu )$ and $H\in L^1({\pi }_{\epsilon })$, the identity ${\Phi }^{\ast }(y)=H(x,y)-\Phi (x)+x\cdot y$ proves ${\Phi }^{\ast }\in L^1(\nu )$ by the marginal distribution property. In particular, no subtraction of infinite integrals is being used.

SetThese are integrable Kantorovich potentials. The Fenchel–Young inequality gives $u(x)+v(y)\le \frac{1}{2}|x-y{|}^2$. More precisely, for every transport plan $\pi$,Taking the infimum in the first inequality therefore provesThe factor $1/2$ in the quadratic cost is essential for this exact gap identity.