Convergence rate analysis of a subgradient averaging algorithm for distributed optimisation with different constraint sets - Romao, L; Margellos, K; Notarstefano, G; Papachristodoulou, A (Institute of Electrical and Electronics Engineers, 2020)
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)=ηk+1, for some η > 0. We then restrict attention to step-size choices c(k)=ηk+1√,η>0, and establish a convergence of (ln(k)k√) 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.