Multi-Step Gradient Methods for Networked Optimization
2013 (English)In: IEEE Transactions on Signal Processing, ISSN 1053-587X, E-ISSN 1941-0476, Vol. 61, no 21, 5417-5429 p.Article in journal (Refereed) Published
We develop multi-step gradient methods for network-constrained optimization of strongly convex functions with Lipschitz-continuous gradients. Given the topology of the underlying network and bounds on the Hessian of the objective function, we determine the algorithm parameters that guarantee the fastest convergence and characterize situations when significant speed-ups over the standard gradient method are obtained. Furthermore, we quantify how uncertainty in problem data at design-time affects the run-time performance of the gradient method and its multi-step counterpart, and conclude that in most cases the multi-step method outperforms gradient descent. Finally, we apply the proposed technique to three engineering problems: resource allocation under network-wide budget constraint, distributed averaging, and Internet congestion control. In all cases, our proposed algorithms converge significantly faster than the state-of-the art.
Place, publisher, year, edition, pages
2013. Vol. 61, no 21, 5417-5429 p.
Distributed optimization, accelerated gradient methods, primal and dual decomposition, fast convergence, robustness analysis
IdentifiersURN: urn:nbn:se:kth:diva-133518DOI: 10.1109/TSP.2013.2278149ISI: 000324934300021ScopusID: 2-s2.0-84885164451OAI: oai:DiVA.org:kth-133518DiVA: diva2:662393
FunderSwedish Research CouncilSwedish Foundation for Strategic Research
QC 201311072013-11-072013-11-062013-11-07Bibliographically approved