Newton's method for optimal transport problem on graphs
This work provides a practical Newton solver for optimal transport on graphs, tackling known numerical challenges, but the approach is incremental as it adapts existing techniques to a specific formulation.
The authors develop a Newton method for dynamical optimal transport on graphs, addressing non-uniqueness of edge variables on cycles and ensuring density positivity via a spanning-tree gauge and upwind discretization. The method is applied to lattice and random graphs, inverse problems, and social network analysis.
In this paper, we study dynamical optimal transport on a connected graph from the perspective of the Benamou-Brenier formulation, where densities are assigned to vertices and velocities to edges. However, directly using Newton's method on the resulting nonlinear systems encounters two potential difficulties: (i) if the graph contains cycles, edge variables are not unique, and (ii) there is no guarantee that the density variables remain positive. To address these challenges, we introduce a finite-difference-type Newton method that eliminates cycle-induced redundancies through a spanning-tree gauge, resulting in a reduced set of independent variables and a well-posed, sparse linear system. For the lattice graph arising from the continuous optimal transport problem, density positivity can also be guaranteed by using an upwind discretization subject to a CFL-type condition. We further demonstrate the versatility of the proposed scheme by applying it to a range of problems, including optimal transport on lattices and random graphs, inverse optimal transport problems, and social network analysis.