Kantorovich Dual problem

The Kantorovich Dual Problem is one of the minimization problems in Optimal Transport . It is a dual problem of the Kantorovich Problem.

The Shipper’s Problem

One of the ways to understand this problem is stated by Caffarelli. The statement is presented in the book by Villani (Villani 2021). We will provide the modern rephrase of his statement.

Every morning, people enjoy a coffee time at home. All in all, it costs Amazon $c(x,y)$ dollars to ship one box of necessary espresso capsules from place $x$ to place $y$, i.e. from warehouses to homes. We want to optimize this expensive habit and consequently to solve appropriate Monge-Kantorovich problem. The mathematicians come to Amazon and propose the new kind of payment. For every box at place $x$ they will charge $\phi (x)$ dollars and $\psi (y)$ dollars to deliver at place $y$. However, mathematicians will not reveal their shipping routes. Of course, in order for Amazon to accept this offer, the price $\phi (x)+\psi (y)\le c(x,y)$. The moral is that if the mathematicians are smart enough, they will be capable to make this shipment cheaper. This is provided by Kantorovich duality theorem. Take care that in the same cases, mathematicians will also give negative prices, if it is necessary!

Statement of Theorem

This is the statement of the Theorem in the book “Topics in Optimal Transportation”, by Cedric Villani (Villani 2021).

Let $X$ and $Y$ be Polish spaces, let $\mu \in \mathcal{P}(X)$ and $\nu \in \mathcal{P}(Y)$, and let a cost function $c:X\times Y\to [0,+\mathrm{\infty }]$ be lower semi-continuous. Whenever $\pi \in \mathcal{P}(X\times Y)$ and $(\phi ,\psi )\in L^1(d\mu )\times L^1(d\nu )$, define $$I[\pi ]={\int }_{X\times Y}c(x,y)d\pi (x,y),J(\phi ,\psi )={\int }_X\phi (x)d\mu (x)+{\int }_Y\psi (y)d\nu (y).$$

Define $\mathrm{\Pi }(\mu ,\nu )$ to be the set of Borel probability measures $\pi$ on $X\times Y$ such that for all measurable sets $A\subset X$ and $B\subset Y$ , $\pi [A\times Y]=\mu (A)$ , $\pi [X\times B]=\nu (B)$ , and define ${\mathrm{\Phi }}_c$ to be the set of all measurable functions $(\phi ,\psi )\in L^1(d\mu )\times L^1(d\nu )$ satisfying $\phi (x)+\psi (y)\le c(x,y)$ for $d\mu$ almost everywhere in $X$ and $d\nu$ almost everywhere in $Y$.

Then $\underset{\mathrm{\Pi }(\mu ,\nu )}{inf}I[\pi ]=\underset{{\mathrm{\Phi }}_c}{sup}J(\phi ,\psi )$.

Moreover, the infimum $\underset{\mathrm{\Pi }(\mu ,\nu )}{inf}I[\pi ]$ is attained. In addition it is possible to restrict $\phi$ and $\psi$ to be continuous and bounded.

Ideas and the techniques used in the proof

First, we assume that our spaces $X$ and $Y$ are compact and that the cost function $c(x,y)$ is continuous. The general case follows by an approximation argument.

The main idea is to use minimax principle, i.e. interchanging inf sup with sup inf in the proof. For this, we need some basic convex analysis techniques, namely Legendre-Fenchel transform and Theorem on Fenchel-Rockafellar Duality (its proof is based on Hahn-Banach theorem consequence on separating convex sets). The required statements can be found in the book by Rockafellar(Rockafellar 1997) and the book by Bauschke and Combettes(Bauschke et al. 2017).

Take a note that at some point we use Arzela-Ascoli Theorem. In a non-compact space this is not possible. In order to evade compactness property, we have to use Prokhorov’s theorem:

Let ${\mu }_n$ be a tight sequence of probability measures on Polish space $X$. Then, there exists $\mu \in \mathcal{P}(X)$ and convergent subsequence ${\mu }_{n_k}$ such that ${\mu }_{n_k}\rightharpoonup \mu$ in the dual of $C_b(X)$. Conversely, every sequence ${\mu }_n\rightharpoonup \mu$ is tight.

The proof of the previous Theorem can be found in (Bogachev and Ruas 2007). For more information on $C_b(X)$ duality, take a look at Dual space of C_0(x) vs C_b(x).

C-concave functions

There are a few alternative proofs of the theorem above. First, we will discuss the conclusion of the Theorem.

In Kantorovich Duality Theorem, the left-hand side of the last equality, the infimum $\underset{\mathrm{\Pi }(\mu ,\nu )}{inf}I[\pi ]$ is attained. For continuous and bounded cost function $c(x,y)$ we can restrict $\underset{{\mathrm{\Phi }}_c}{sup}J(\phi ,\psi )$ to pairs $({\phi }^{cc},{\phi }^c)$ where $\phi$ is bounded and

$${\phi }^c(y)=\underset{y\in Y}{inf}[c(x,y)-\phi (x)],{\phi }^{cc}(x)=\underset{y\in Y}{inf}[c(x,y)-{\phi }^c(y)].$$

The pair $({\phi }^{cc},{\phi }^c)$ is called a pair of conjugate c-concave functions. This way we improve the maximization functions for the dual problem (for motivation, think about shipper’s problem). It is known that under the reasonable assumptions ${\phi }^{cc}=\phi$ and that ${\phi }^c$ is measurable, see (Santambrogio 2015).

Hence, it is possible to state the Kantorovich Duality theorem using c-concave functions: $$\text{max}(DP)={\text{max}}_{\phi \in c-conc(X)}{\int }_X\phi (x)d\mu +{\int }_Y{\phi }^c(y)d\nu$$

References

Bauschke, Heinz H, Patrick L Combettes, Heinz H Bauschke, and Patrick L Combettes. 2017. Correction to: Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer.

Bogachev, Vladimir Igorevich, and Maria Aparecida Soares Ruas. 2007. Measure Theory. Vol. 1. 1. Springer.

Rockafellar, R Tyrrell. 1997. Convex Analysis. Vol. 28. Princeton university press.

Santambrogio, Filippo. 2015. Optimal Transport for Applied Mathematicians. Vol. 87. Springer.

Villani, Cédric. 2021. Topics in Optimal Transportation. Vol. 58. American Mathematical Soc.