A Semismooth Newton-AMG Based Primal-dual Algorithm for Generalized Transport Problems
发布时间：2021年12月16日
浏览次数：4528
发布者: He Liu
主讲人： Hao LUO(PKU)
活动时间： 从 2021-12-22 15:15 到 17:00
场地： 北京国际数学研究中心，全斋全29教室
We consider a large class of transport like problems including assignment problem, Monge-Kantorovich mass transport, partial optimal transport and capacity constrained transport problem. A (super) linearly convergent inexact primal-dual algorithm is proposed via implicit Euler discretization of a proper dynamical system. The subproblem is solved by the semismooth Newton iteration and the corresponding linear system possesses hidden graph Laplacian structure which motivates us to adopt efficient AMG solver. In particular, by using the well-known X-Z identity, we establish the uniform convergence rate of a two-grid method.
