Skip to main content

Approximate augmented lagrangians for distributed network optimization

Publication ,  Journal Article
Chatzipanagiotis, N; Dentcheva, D; Zavlanos, MM
Published in: Proceedings of the IEEE Conference on Decision and Control
January 1, 2012

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.

Duke Scholars

Published In

Proceedings of the IEEE Conference on Decision and Control

DOI

EISSN

2576-2370

ISSN

0743-1546

Publication Date

January 1, 2012

Start / End Page

5840 / 5845
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Chatzipanagiotis, N., Dentcheva, D., & Zavlanos, M. M. (2012). Approximate augmented lagrangians for distributed network optimization. Proceedings of the IEEE Conference on Decision and Control, 5840–5845. https://doi.org/10.1109/CDC.2012.6426203
Chatzipanagiotis, N., D. Dentcheva, and M. M. Zavlanos. “Approximate augmented lagrangians for distributed network optimization.” Proceedings of the IEEE Conference on Decision and Control, January 1, 2012, 5840–45. https://doi.org/10.1109/CDC.2012.6426203.
Chatzipanagiotis N, Dentcheva D, Zavlanos MM. Approximate augmented lagrangians for distributed network optimization. Proceedings of the IEEE Conference on Decision and Control. 2012 Jan 1;5840–5.
Chatzipanagiotis, N., et al. “Approximate augmented lagrangians for distributed network optimization.” Proceedings of the IEEE Conference on Decision and Control, Jan. 2012, pp. 5840–45. Scopus, doi:10.1109/CDC.2012.6426203.
Chatzipanagiotis N, Dentcheva D, Zavlanos MM. Approximate augmented lagrangians for distributed network optimization. Proceedings of the IEEE Conference on Decision and Control. 2012 Jan 1;5840–5845.

Published In

Proceedings of the IEEE Conference on Decision and Control

DOI

EISSN

2576-2370

ISSN

0743-1546

Publication Date

January 1, 2012

Start / End Page

5840 / 5845