Convergence rate for distributed optimization methods: Novel bounds and distributed step size computation

Yu Sun, Alberto Speranzon, Prashant Girdharilal Mehta

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

We consider unconstrained multi-agent optimization problems where agents cooperatively minimize the sum of their local objective functions. By combining and extending recent results in [1] and [2], we determine an improved bound on the convergence rate of consensus based distributed subgradient methods with constant step size. In particular, we show that the convergence speed of the consensus based algorithm and the asymptotic optimization error are jointly decided by the step size and the spectral gap of the underlying network. Wave equation based algorithm [3] is utilized to rapidly and distributively compute the proposed bound, thus providing a way for the agents to estimate the instantaneous error as well as chose a suitable step size in a distributed fashion. Simulation results show how the bound compares to ground truth values for some relevant examples.

Original languageEnglish (US)
Title of host publication2012 American Control Conference, ACC 2012
Pages3712-3717
Number of pages6
StatePublished - Nov 26 2012
Event2012 American Control Conference, ACC 2012 - Montreal, QC, Canada
Duration: Jun 27 2012Jun 29 2012

Publication series

NameProceedings of the American Control Conference
ISSN (Print)0743-1619

Other

Other2012 American Control Conference, ACC 2012
CountryCanada
CityMontreal, QC
Period6/27/126/29/12

ASJC Scopus subject areas

  • Electrical and Electronic Engineering

Fingerprint Dive into the research topics of 'Convergence rate for distributed optimization methods: Novel bounds and distributed step size computation'. Together they form a unique fingerprint.

Cite this