Kantorovich duality

Remarks

The left side is the Kantorovich form of the optimal transport problem, and the right side is its dual. The inequality $\ge$ is easy: if $\varphi(x) + \psi(y) \le c(x, y)$ and $\pi \in \Pi(\mu, \nu)$, integrating against $\pi$ gives $\int \varphi \, d\mu + \int \psi \, d\nu \le \int c \, d\pi$. The reverse inequality is a minimax argument. For compact spaces and continuous $c$ it follows from a duality theorem of convex analysis, such as the Fenchel–Rockafellar theorem. The general case follows by approximation. Example: if $\mu = \delta_a$ is a Dirac mass, the only coupling is $\delta_a \otimes \nu$, so the left side equals $\int c(a, y) \, d\nu(y)$. When $X = Y$ and $c$ is a metric $d$, the dual can be taken over $\psi = -\varphi$ with $\varphi$ $1$-Lipschitz, which is the Kantorovich–Rubinstein duality. Lower semicontinuity of $c$ is used to show that the minimum is attained, through the weak compactness of $\Pi(\mu, \nu)$.

Going deeper

For a student

Kantorovich duality is the linear-programming duality of optimal transport, extended to infinite spaces. Under mild integrability conditions on $c$, optimal dual pairs $(\varphi, \psi)$ exist and can be chosen $c$-concave, and an optimal plan is concentrated on the set where $\varphi(x) + \psi(y) = c(x, y)$. This is the starting point for Brenier's theorem, where the optimal $\varphi$ gives the optimal map, and for the theory of Wasserstein distances.