Title :
Accelerated gradient methods for networked optimization
Author :
Ghadimi, E. ; Johansson, M. ; Shames, I.
Author_Institution :
ACCESS Linnaeus Center, R. Inst. of Technol., Stockholm, Sweden
fDate :
June 29 2011-July 1 2011
Abstract :
This paper explores the use of accelerated gradient methods in networked optimization. Optimal algorithm parameters and associated convergence rates are derived for distributed resource allocation and consensus problems, and the practical performance of the accelerated gradient algorithms are shown to outperform alternatives in the literature. Since the optimal parameters for the accelerated gradient method depends on upper and lower bounds of the Hessian, we study how errors in these estimates influence the convergence rate of the algorithm. This analysis identifies, among other things, cases where erroneous estimates of the Hessian bounds cause the accelerated method to have slower convergence than the corresponding (non-accelerated) gradient method. An application to Internet congestion control illustrates these issues.
Keywords :
Hessian matrices; gradient methods; optimisation; Hessian bounds; Internet congestion control; accelerated gradient algorithm; accelerated gradient method; consensus problems; convergence rates; distributed resource allocation; networked optimization; optimal algorithm parameter; Acceleration; Algorithm design and analysis; Convergence; Gradient methods; Laplace equations; Resource management;
Conference_Titel :
American Control Conference (ACC), 2011
Conference_Location :
San Francisco, CA
Print_ISBN :
978-1-4577-0080-4
DOI :
10.1109/ACC.2011.5990992