Approximate augmented lagrangians for distributed network optimization

In this paper, we propose a distributed algorithm for optimal routing in wireless multi-hop networks. We build our approach on a recently proposed model for stochastic routing, whereby each node selects a neighbor to forward a packet according to a given probability distribution. Our solution relies on dual decomposition techniques with regularization, that can significantly improve on the slow convergence of subgradient methods. In particular, we employ the method of augmented Lagrangians (AL). While regularization introduces coupling of the primal variables, a recently proposed iterative approximation technique can be used to decouple the minimization problem in the augmented Lagrangian method (ALM). Once the approximation reaches a predetermined number of iterations it is terminated and followed by a novel update of the Lagrange multipliers, that differs from that in the standard ALM. We show that truncating the approximation is necessary to obtain a fully distributed approach, and that the proposed update of the Lagrange multipliers is critical to obtain convergence of our method. An additional advantage of our approach is that convergence is very fast even for sparse networks, where techniques that incorporate consensus iterations into the algorithm tend to be slow.