Optimal Transport with Constraints: From Mirror Descent to Classical Mechanics

Abstract

Finding optimal trajectories for multiple traffic demands in a congested network is a challenging task. Optimal transport theory is a principled approach that has been used successfully to study various transportation problems. Its usage is limited by the lack of principled and flexible ways to incorporate realistic constraints. We propose a principled physics-based approach to impose constraints flexibly in such optimal transport problems. Constraints are included in mirror descent dynamics using the principle of D’Alembert-Lagrange from classical mechanics. This leads to a sparse, local and linear approximation of the feasible set leading in many cases to closed-form updates.