Effcient primal-dual algorithms for optimal transport-like problems
Date:
In this report, we focus on effcient algorithms for solving a large class of optimal transport-like problems. We will first introduce some primal-dual flow models and equip them with proper Lyapunov functions that possess exponential decay property. Then, based on time discretizations of the continuous dynamics, we obtain new primal-dual methods and prove the nonergodic ((super-)linear or sublinear)convergence rates. Besides, by exploring the special structure, the inner problems of the proposed methods either admit closed solution or can be solved by the semi-smooth Newton iteration with algebraic multigrid method. Moreover, numerical experiments are provided to validate the effciency of our algorithms.