Metraipolis › archive › dc_5111104bbc4f

A Multiscale Primal-Dual Interior-Point Relaxation Method for Large-Scale Optimal Transport Problems — arXiv:2608.12060

Source: arXiv (en)
Original: https://arxiv.org/abs/2608.12060
License (as archived): CC0-1.0
Archived: 2026-10-19T05:44:16.980Z
SHA-256 of the archived text: 6301096fc04fcae5484b2eb42a4fad4d269ed51804d336c11d772d81599243e4
Stable URL of this page: https://metraipolis.com/documento/dc_5111104bbc4f

How to cite

A Multiscale Primal-Dual Interior-Point Relaxation Method for Large-Scale Optimal Transport Problems — arXiv:2608.12060 — arXiv (en), https://arxiv.org/abs/2608.12060 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5111104bbc4f (Metraipolis archive dc_5111104bbc4f, sha256 6301096fc04fcae5484b2eb42a4fad4d269ed51804d336c11d772d81599243e4)

BibTeX

@misc{dc5111104bbc4f,
  title = {A Multiscale Primal-Dual Interior-Point Relaxation Method for Large-Scale Optimal Transport Problems — arXiv:2608.12060},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.12060},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5111104bbc4f; sha256 6301096fc04fcae5484b2eb42a4fad4d269ed51804d336c11d772d81599243e4},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.12060. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Large-scale optimal transport (OT) problems involve a vast number of transport variables, leading to prohibitive memory and computational costs. To address these challenges, we propose a multiscale primal-dual interior-point relaxation method (MSIPRM). The multiscale outer framework constructs a hierarchy of standard OT problems at progressively finer levels. At each level, the OT problem is solved over a sequence of adaptively refined active sets initialized based on the solution support at the previous level. This yields a sequence of closely related sparse subproblems, thereby substantially reducing memory requirements. The primal-dual interior-point relaxation method (IPRM) serves as the inner solver for each sparse subproblem. Since IPRM does not require strictly interior iterates, it can readily use the solution of the previous subproblem as a warm start. To efficiently obtain the Newton direction, we solve a reduced Schur complement system derived from the normal equations. Furthermore, we develop an effective support-identification strategy based on the approximate solutions obtained by IPRM. We establish condition number estimates for the Schur complement matrices and analyze the global and local convergence properties of the algorithm. Numerical experiments on large-scale test problems demonstrate the computational efficiency and scalability of MSIPRM and show that it compares favorably with existing solvers. In particular, MSIPRM can handle instances whose full formulations contain trillions of transport variables.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-13 in math.OC).
Categorie arXiv: Optimization and Control (math.OC).
Pagina del lavoro: https://arxiv.org/abs/2608.12060 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-19T05:39:32.140Z dalla pagina https://arxiv.org/catchup/math.OC/2026-08-13?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).