Change search
ReferencesLink to record
Permanent link

Direct link
Multi-Step Gradient Methods for Networked Optimization
KTH, School of Electrical Engineering (EES), Automatic Control.
KTH, School of Electrical Engineering (EES), Automatic Control.
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
Abstract [en]

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.
Keyword [en]
Distributed optimization, accelerated gradient methods, primal and dual decomposition, fast convergence, robustness analysis
National Category
Signal Processing
URN: urn:nbn:se:kth:diva-133518DOI: 10.1109/TSP.2013.2278149ISI: 000324934300021ScopusID: 2-s2.0-84885164451OAI: diva2:662393
Swedish Research CouncilSwedish Foundation for Strategic Research

QC 20131107

Available from: 2013-11-07 Created: 2013-11-06 Last updated: 2013-11-07Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Ghadimi, EuhannaJohansson, Mikael
By organisation
Automatic Control
In the same journal
IEEE Transactions on Signal Processing
Signal Processing

Search outside of DiVA

GoogleGoogle Scholar
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

Altmetric score

Total: 59 hits
ReferencesLink to record
Permanent link

Direct link