An efficient second-order cone programming approach for dynamic optimal transport on staggered grid discretization
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916032300449792 |
|---|---|
| author | Chen, Liang Lin, Youyicun Zhou, Yuxuan |
| author_facet | Chen, Liang Lin, Youyicun Zhou, Yuxuan |
| contents | This paper proposes an efficient numerical method based on second-order cone programming (SOCP) to solve dynamic optimal transport (DOT) problems with quadratic cost on staggered grid discretization. By properly reformulating discretized DOT problems into a linear SOCP, the proposed method eliminates the interpolation matrices and thus avoids solving a series of cubic equations and linear systems induced by interpolation. Then, by taking advantage of the SOCP reformulation, we can solve them efficiently by a computationally highly economical implementation of an inexact decomposition-based proximal augmented Lagrangian method. Moreover, we have made the proposed approach an open-source software package. Numerical experiments on various DOT problems suggest that the proposed approach performs significantly more efficiently than state-of-the-art software packages. In addition, it exhibits prominent robustness to problems with non-negative measures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05424 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | An efficient second-order cone programming approach for dynamic optimal transport on staggered grid discretization Chen, Liang Lin, Youyicun Zhou, Yuxuan Optimization and Control 90C25, 90C06, 90-04, 65K05, 49Q22 This paper proposes an efficient numerical method based on second-order cone programming (SOCP) to solve dynamic optimal transport (DOT) problems with quadratic cost on staggered grid discretization. By properly reformulating discretized DOT problems into a linear SOCP, the proposed method eliminates the interpolation matrices and thus avoids solving a series of cubic equations and linear systems induced by interpolation. Then, by taking advantage of the SOCP reformulation, we can solve them efficiently by a computationally highly economical implementation of an inexact decomposition-based proximal augmented Lagrangian method. Moreover, we have made the proposed approach an open-source software package. Numerical experiments on various DOT problems suggest that the proposed approach performs significantly more efficiently than state-of-the-art software packages. In addition, it exhibits prominent robustness to problems with non-negative measures. |
| title | An efficient second-order cone programming approach for dynamic optimal transport on staggered grid discretization |
| topic | Optimization and Control 90C25, 90C06, 90-04, 65K05, 49Q22 |
| url | https://arxiv.org/abs/2505.05424 |