Approximate augmented lagrangians for distributed network optimization

Journal Article

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. © 2012 IEEE.

Full Text

Duke Authors

Cited Authors

  • Chatzipanagiotis, N; Dentcheva, D; Zavlanos, MM

Published Date

  • January 1, 2012

Published In

Start / End Page

  • 5840 - 5845

Electronic International Standard Serial Number (EISSN)

  • 2576-2370

International Standard Serial Number (ISSN)

  • 0743-1546

Digital Object Identifier (DOI)

  • 10.1109/CDC.2012.6426203

Citation Source

  • Scopus