Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Communication Complexity of Dual Decomposition Methods for Distributed Resource Allocation Optimization
KTH, School of Electrical Engineering and Computer Science (EECS).
Harvard Univ, Sch Engn & Appl Sci, Cambridge, MA 02138 USA..
Harvard Univ, Sch Engn & Appl Sci, Cambridge, MA 02138 USA..
KTH, School of Electrical Engineering and Computer Science (EECS).ORCID iD: 0000-0001-9810-3478
Show others and affiliations
2018 (English)In: IEEE Journal on Selected Topics in Signal Processing, ISSN 1932-4553, E-ISSN 1941-0484, Vol. 12, no 4, p. 717-732Article in journal (Refereed) Published
Abstract [en]

Dual decomposition methods are among the most prominent approaches for finding primal/dual saddle point solutions of resource allocation optimization problems. To deploy these methods in the emerging Internet of things networks, which will often have limited data rates, it is important to understand the communication overhead they require. Motivated by this, we introduce and explore twomeasures of communication complexity of dual decomposition methods to identify the most efficient communication among these algorithms. The first measure is epsilon-complexity, which quantifies the minimal number of bits needed to find an epsilon-accurate solution. The second measure is b-complexity, which quantifies the best possible solution accuracy that can be achieved from communicating b bits. We find the exact epsilon -and b-complexity of a class of resource allocation problems where a single supplier allocates resources to multiple users. For both the primal and dual problems, the epsilon-complexity grows proportionally to log(2) (1/epsilon) and the b-complexity proportionally to 1/2(b). We also introduce a variant of the epsilon- and b-complexity measures where only algorithms that ensure primal feasibility of the iterates are allowed. Such algorithms are often desirable because overuse of the resources can overload the respective systems, e.g., by causing blackouts in power systems. We provide upper and lower bounds on the convergence rate of these primal feasible complexity measures. In particular, we show that the b-complexity cannot converge at a faster rate than O(1/b). Therefore, the results demonstrate a tradeoff between fast convergence and primal feasibility. We illustrate the result by numerical studies.

Place, publisher, year, edition, pages
Institute of Electrical and Electronics Engineers (IEEE), 2018. Vol. 12, no 4, p. 717-732
Keywords [en]
Distributed optimization, networked systems, resource allocation, communication complexity
National Category
Communication Systems
Identifiers
URN: urn:nbn:se:kth:diva-233281DOI: 10.1109/JSTSP.2018.2848718ISI: 000440807600012Scopus ID: 2-s2.0-85048639200OAI: oai:DiVA.org:kth-233281DiVA, id: diva2:1240347
Note

QC 20180821

Available from: 2018-08-21 Created: 2018-08-21 Last updated: 2018-08-21Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Authority records BETA

Fischione, Carlo

Search in DiVA

By author/editor
Magnusson, SindriFischione, Carlo
By organisation
School of Electrical Engineering and Computer Science (EECS)
In the same journal
IEEE Journal on Selected Topics in Signal Processing
Communication Systems

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 15 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • harvard1
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf