pipette
ESEspañol

A Logarithmic-dual-update Bregman ADMM for Optimal Transport

Di Hou, Kim-Chuan Toh

Preprint

In the authors' words

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, we establish -linear convergence of the primal--dual sequence for general OT costs with any fixed multiplier stepsize in 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 kernel structure to accelerate matrix--vector products and reduce storage requirements. Numerical experiments show competitive performance for general cost matrices and 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 grid points in each marginal, is solved in approximately 100 seconds on a single GPU.

Main resultThe abstract does not state a limitation.

Appeared: Wednesday, October 7. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 49 pages, 2 figures