An ADMM-Based Approach to Quadratically-Regularized Distributed Optimal Transport on Graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911040115048448 |
|---|---|
| author | Mokhtari, Yacine Moulay, Emmanuel Coirault, Patrick Ny, Jérôme Le |
| author_facet | Mokhtari, Yacine Moulay, Emmanuel Coirault, Patrick Ny, Jérôme Le |
| contents | Optimal transport on a graph focuses on finding the most efficient way to transfer resources from one distribution to another while considering the graph's structure. This paper introduces a new distributed algorithm that solves the optimal transport problem on directed, strongly connected graphs, unlike previous approaches which were limited to bipartite graphs. Our algorithm incorporates quadratic regularization and guarantees convergence using the Alternating Direction Method of Multipliers (ADMM). Notably, it proves convergence not only with quadratic regularization but also in cases without it, whereas earlier works required strictly convex objective functions.
In this approach, nodes are treated as agents that collaborate through local interactions to optimize the total transportation cost, relying only on information from their neighbors. Through numerical experiments, we show how quadratic regularization affects both convergence behavior and solution sparsity under different graph structures. Additionally, we provide a practical example that highlights the algorithm's robustness through its ability to adjust to topological changes in the graph. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_05509 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An ADMM-Based Approach to Quadratically-Regularized Distributed Optimal Transport on Graphs Mokhtari, Yacine Moulay, Emmanuel Coirault, Patrick Ny, Jérôme Le Optimization and Control Numerical Analysis 68W15, 93A14, 93D50, 49Q22, 05C21 Optimal transport on a graph focuses on finding the most efficient way to transfer resources from one distribution to another while considering the graph's structure. This paper introduces a new distributed algorithm that solves the optimal transport problem on directed, strongly connected graphs, unlike previous approaches which were limited to bipartite graphs. Our algorithm incorporates quadratic regularization and guarantees convergence using the Alternating Direction Method of Multipliers (ADMM). Notably, it proves convergence not only with quadratic regularization but also in cases without it, whereas earlier works required strictly convex objective functions. In this approach, nodes are treated as agents that collaborate through local interactions to optimize the total transportation cost, relying only on information from their neighbors. Through numerical experiments, we show how quadratic regularization affects both convergence behavior and solution sparsity under different graph structures. Additionally, we provide a practical example that highlights the algorithm's robustness through its ability to adjust to topological changes in the graph. |
| title | An ADMM-Based Approach to Quadratically-Regularized Distributed Optimal Transport on Graphs |
| topic | Optimization and Control Numerical Analysis 68W15, 93A14, 93D50, 49Q22, 05C21 |
| url | https://arxiv.org/abs/2410.05509 |