Dual potentials for capacity constrained optimal transport

Abstract

Optimal transportation with capacity constraints, a variant of the well-known optimal transportation problem, is concerned with transporting one probability density $f\in L^1({\mathbb{R}}^m)$ onto another one $g\in L^1({\mathbb{R}}^n)$ so as to optimize a cost function $c\in L^1({\mathbb{R}}^{m+n})$ while respecting the capacity constraints $0\le h\le \bar{h}\in L^{\infty }({\mathbb{R}}^{m+n})$. A linear programming duality theorem for this problem was first established by Levin. In this note, we prove under mild assumptions on the given data, the existence of a pair of $L^1$-functions optimizing the dual problem. Using these functions, which can be viewed as Lagrange multipliers to the marginal constraints $f$ and $g$, we characterize the solution $h$ of the primal problem. We expect these potentials to play a key role in any further analysis of $h$. Moreover, starting from Levin's duality, we derive the classical Kantorovich duality for unconstrained optimal transport. In tandem with results obtained in our companion paper (arXiv:1309.3022), this amounts to a new and elementary proof of Kantorovich's duality.

Revised version

References in corpus (2)

• Insights into capacity constrained optimal transport
• A penalization approach to linear programming duality with application to capacity constrained transport

Cited by in corpus (1)

• A penalization approach to linear programming duality with application to capacity constrained transport