TY - JOUR
T1 - Approximate augmented lagrangians for distributed network optimization
AU - Chatzipanagiotis, Nikolaos
AU - Dentcheva, Darinka
AU - Zavlanos, Michael M.
PY - 2012
Y1 - 2012
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=84874242709&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84874242709&partnerID=8YFLogxK
U2 - 10.1109/CDC.2012.6426203
DO - 10.1109/CDC.2012.6426203
M3 - Conference article
AN - SCOPUS:84874242709
SN - 0743-1546
SP - 5840
EP - 5845
JO - Proceedings of the IEEE Conference on Decision and Control
JF - Proceedings of the IEEE Conference on Decision and Control
M1 - 6426203
T2 - 51st IEEE Conference on Decision and Control, CDC 2012
Y2 - 10 December 2012 through 13 December 2012
ER -