A Logarithmic-dual-update Bregman ADMM for Optimal Transport
Abstract
This paper studies an entropy Bregman alternating direction method of multipliers (BADMM) with logarithmic dual update for solving discrete optimal transport (OT) problems. The algorithm uses simple row and column normalizations without inner iterations, allowing efficient CPU and GPU implementations. However, the convergence of this method for general OT problems has not been established. Starting from a strictly positive feasible primal point and a zero multiplier, here we establish the R-linear convergence of the primal--dual sequence for general OT costs with any fixed multiplier stepsize in (0,2) and a sufficiently large fixed penalty, even when the primal limit lies on the boundary. Our analysis further characterizes the primal limit as the entropy Bregman projection of the initial point onto the optimal solution set and establishes strict complementarity of the limiting OT primal--dual solution. For separable costs on two-dimensional grids, we exploit the separable structure to accelerate matrix--vector products and reduce storage requirements. Numerical experiments show competitive performance of our BADMM for general cost matrices with substantial speedups over state-of-the-art solvers, including HOT and HALO, for squared Euclidean costs on two-dimensional-grid marginals. The largest tested problem, with 2048×2048 ≈ 4.19M grid points in each marginal, is solved in approximately 100 seconds on a single GPU.
Related
- GPU-Accelerated Bregman Douglas-Rachford Splitting for Discrete Optimal Transport
- Stability of the Monge Map in Semi-Dual Optimal Transport
- Dual-Inertial Bregman Methods with Energy-Based Safeguarding
- Accelerated Bregman Proximal Gradient Methods from Dual Geometric Perspectives
- Soft-Update MSA for Nonconvex Stochastic Optimal Control: Theory and Algorithms
BibTeX
@misc{hou2026logarithmicdualupdate,
title = {{A Logarithmic-dual-update Bregman ADMM for Optimal Transport}},
author = {Di Hou and Kim-Chuan Toh},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.08087},
eprint = {2610.08087},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.08087},
}
RIS
TY - UNPB
TI - A Logarithmic-dual-update Bregman ADMM for Optimal Transport
AU - Di Hou
AU - Kim-Chuan Toh
PY - 2026
DA - 2026/10/12
PB - arXiv
DO - 10.48550/arxiv.2610.08087
UR - https://arxiv.org/abs/2610.08087
AB - This paper studies an entropy Bregman alternating direction method of multipliers (BADMM) with logarithmic dual update for solving discrete optimal transport (OT) problems. The algorithm uses simple row and column normalizations without inner iterations, allowing efficient CPU and GPU implementations. However, the convergence of this method for general OT problems has not been established. Starting from a strictly positive feasible primal point and a zero multiplier, here we establish the R-linear convergence of the primal--dual sequence for general OT costs with any fixed multiplier stepsize in (0,2) and a sufficiently large fixed penalty, even when the primal limit lies on the boundary. Our analysis further characterizes the primal limit as the entropy Bregman projection of the initial point onto the optimal solution set and establishes strict complementarity of the limiting OT primal--dual solution. For separable costs on two-dimensional grids, we exploit the separable structure to accelerate matrix--vector products and reduce storage requirements. Numerical experiments show competitive performance of our BADMM for general cost matrices with substantial speedups over state-of-the-art solvers, including HOT and HALO, for squared Euclidean costs on two-dimensional-grid marginals. The largest tested problem, with 2048×2048 ≈ 4.19M grid points in each marginal, is solved in approximately 100 seconds on a single GPU.
ER -