Distributed Newton for Network Flow Optimisation

back to our research

Distributed Newton for Network Flow Optimisation

(No date yet – To appear)

(not yet available online)

SIAM Journal on Optimisation

Authors: Rasul Tutunov, Haitham Bou-Ammar (PROWLER.io), and Ali Jadbabaie 

Abstract: In this paper, we propose a new distributed second-order method for network flow optimization. Our algorithm exploits the symmetry and diagonal dominance property of the dual Hessian to determine the Newton direction in a distributed fashion up-to-any precision ε > 0. This is achieved by first introducing a novel distributed solver for systems of equations described by symmetric diagonally dominant matrices based on Chebyshev polynomials. Our solver is then used to compute the Newton direction leading to a novel algorithm exhibiting similar phases of convergence to the exact (i.e., centralized) Newton method. We rigorously analyze the theoretical properties of both the solver and the distributed Newton method. Finally, we provide empirical validation for the proposed technique on a variety of network topologies.

Data Efficiency

Graph Theory

Network Flow


See paper