Accelerated dual descent for constrained convex network flow optimization

We present a fast distributed solution to the capacity constrained convex network flow optimization problem. Our solution is based on a distributed approximation of Newtons method called Accelerated Dual Descent (ADD). Our algorithm uses a parameterized approximate inverse Hessian, which is computed using matrix splitting techniques and a Neumann series truncated after N terms. The algorithm is called ADD-N because each update requires information from N-hop neighbors in the network. The parameter N characterizes an explicit trade off between information dependence and convergence rate. Numerical experiments show that even for N=1 and N=2, ADD-N converges orders of magnitude faster than subgradient descent.