Bregman Douglas Rachford Splitting

GPU-Accelerated Bregman Douglas–Rachford Splitting for Discrete Optimal Transport

Categories Convex and Nonsmooth Optimization, Optimization Software and Modeling Systems Tags , ,

We present GPU-accelerated Bregman Douglas–Rachford splitting algorithm (BDRS) for discrete optimal transport problem in three input formats: an explicit cost matrix, a point cloud with a ground cost between them, and a separable cost on a regular grid. For each input format, we propose hardware-aware designs of mathematically equivalent representations for the BDRS iterations to … Read more

BDRS Can Fail for Matrix Scaling and Optimal Transport

Categories Convex Optimization Tags , ,

We show that the Bregman Douglas–Rachford splitting method (BDRS) can fail for matrix scaling and unregularized optimal transport. For matrix scaling, we construct a strictly positive \(36\times6\) integer matrix, positive rational marginals of equal mass, and a positive auxiliary initialization for which the matrix iterates enter a nonconstant six-cycle after one iteration. The construction prescribes … Read more