Kantorovich Dual Problem (for general costs)

Introduction

The main advantage of Kantorovich Problem, in comparison to Monge problem, is in the convex constraint property. It is possible to formulate the dual problem.

The Shipper's Problem

Type of this problem is stated by Caffarelli. We will provide the modern one.

During the pandemic, people are in the lockdown and it is the best time to enjoy a coffee time. 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 $\varphi (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 $\varphi (x)+\psi (y)\leq 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!

Statement of Theorem

Theorem. 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\rightarrow [0,+\infty ]$ be lower semi-continuous.

Whenever $\pi \in {\mathcal {P}}(X\times Y)$ and $(\varphi ,\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),\quad J(\varphi ,\psi )=\int _{X}\varphi (x)d\mu (x)+\int _{Y}\psi (y)d\nu (y)$.

Define $\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 $\Phi _{c}$ to be the set of all measurable functions $(\varphi ,\psi )\in L^{1}(d\mu )\times L^{1}(d\nu )$ satisfying $\varphi (x)+\psi (y)\leq c(x,y)$ for $d\mu$ almost everywhere in X and $d\nu$ almost everywhere in Y.

Then $inf_{\Pi (\mu ,\nu )}I[\pi ]=sup_{\Phi _{c}}J(\varphi ,\psi )$.

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

References

</ references>