An efficient second-order cone programming approach for dynamic optimal transport on staggered grid discretization
摘要
This paper proposes an efficient numerical optimization method based on second-order cone programming (SOCP) to solve dynamic optimal transport (DOT) problems with quadratic costs on staggered grid discretizations. By properly reformulating the discretized DOT problem into an equivalent linear SOCP, we develop a highly efficient implementation of an inexact decomposition-based proximal augmented Lagrangian method to solve it. The proposed approach is provided as an open-source software package to facilitate reproducibility and further research. Numerical experiments on a diverse range of DOT problems demonstrate that our software significantly outperforms several state-of-the-art solvers in terms of both accuracy and computational efficiency. Furthermore, it exhibits robust performance when handling measures that are not strictly positive or are in irregular domains with obstacles.