We consider a multi-agent setting with agents exchanging information over a network to solve a convex constrained optimisation problem in a distributed manner. We analyse a new algorithm based on local subgradient exchange under undirected time-varying communication. First, we prove asymptotic convergence of the iterates to a minimum of the given optimisation problem for time-varying step-sizes of the form c(k) = rac{eta }{{k + 1}}, for some η > 0. We then restrict attention to step-size choices c(k) = rac{eta }{{sqrt {k + 1} }},eta > 0, and establish a convergence of mathcal{O}left( {rac{{ln (k)}}{{sqrt k }}} ight) in objective value. Our algorithm extends currently available distributed subgradient/proximal methods by: (i) accounting for different constraint sets at each node, and (ii) enhancing the convergence speed thanks to a subgradient averaging step performed by the agents. A numerical example demonstrates the efficacy of the proposed algorithm.
Romao L., Margellos K., Notarstefano G., Papachristodoulou A. (2019). Convergence rate analysis of a subgradient averaging algorithm for distributed optimisation with different constraint sets. IEEE [10.1109/CDC40024.2019.9029252].
Convergence rate analysis of a subgradient averaging algorithm for distributed optimisation with different constraint sets
Notarstefano G.;
2019
Abstract
We consider a multi-agent setting with agents exchanging information over a network to solve a convex constrained optimisation problem in a distributed manner. We analyse a new algorithm based on local subgradient exchange under undirected time-varying communication. First, we prove asymptotic convergence of the iterates to a minimum of the given optimisation problem for time-varying step-sizes of the form c(k) = rac{eta }{{k + 1}}, for some η > 0. We then restrict attention to step-size choices c(k) = rac{eta }{{sqrt {k + 1} }},eta > 0, and establish a convergence of mathcal{O}left( {rac{{ln (k)}}{{sqrt k }}} ight) in objective value. Our algorithm extends currently available distributed subgradient/proximal methods by: (i) accounting for different constraint sets at each node, and (ii) enhancing the convergence speed thanks to a subgradient averaging step performed by the agents. A numerical example demonstrates the efficacy of the proposed algorithm.File | Dimensione | Formato | |
---|---|---|---|
CDC_post_review_disclaimer.pdf
accesso aperto
Tipo:
Postprint
Licenza:
Licenza per accesso libero gratuito
Dimensione
388.74 kB
Formato
Adobe PDF
|
388.74 kB | Adobe PDF | Visualizza/Apri |
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.