TY - GEN

T1 - Convergence rate for distributed optimization methods

T2 - 2012 American Control Conference, ACC 2012

AU - Sun, Yu

AU - Speranzon, Alberto

AU - Mehta, Prashant Girdharilal

PY - 2012/11/26

Y1 - 2012/11/26

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84869462180&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84869462180&partnerID=8YFLogxK

M3 - Conference contribution

AN - SCOPUS:84869462180

SN - 9781457710957

T3 - Proceedings of the American Control Conference

SP - 3712

EP - 3717

BT - 2012 American Control Conference, ACC 2012

Y2 - 27 June 2012 through 29 June 2012

ER -