| Abstract: |
| This talk introduces an efficient numerical approach to solve dynamic optimal transport (DOT) problems with quadratic cost in Euclidean spaces or on surfaces, computing both the quadratic Wasserstein distance and the associated displacement interpolation. Building on the convex DOT model of Benamou and Brenier, we reformulate the discretized dual DOT problem to a linear second-order cone programming (SOCP) problem. Then, by taking advantage of the SOCP reformulation, we can solve them efficiently by a computationally highly economical implementation of an inexact symmetric Gauss-Seidel decomposition-based proximal augmented Lagrangian method, which converges to a Karush-Kuhn-Tucker solution without any additional assumptions. Implemented as open-source software packages, the proposed approach demonstrates robustness, effectiveness, and superior computational efficiency in extensive numerical experiments on various datasets, achieving a several-fold speed-up over the state-of-the-art solvers. Additionally, it exhibits robustness to problems with densities that lack a positive lower bound. |
|