A Semismooth Newton-AMG Based Primal-dual Algorithm for Generalized Transport Problems
Time: 2021-12-16
Published By: He Liu
Speaker(s): Hao LUO(PKU)
Time: 15:15-17:00 December 22, 2021
Venue: Room 29, Quan Zhai, BICMR
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.
