A tutorial on decomposition methods for network utility maximization

Daniel P. Palomar, Mung Chiang

Research output: Contribution to journalArticle

1107 Scopus citations

Abstract

A systematic understanding of the decomposability structures in network utility maximization is key to both resource allocation and functionality allocation. It helps us obtain the most appropriate distributed algorithm for a given network resource allocation problem, and quantifies the comparison across architectural alternatives of modularized network design. Decomposition theory naturally provides the mathematical language to build an analytic foundation for the design of modularized and distributed control of networks. In this tutorial paper, we first review the basics of convexity, Lagrange duality, distributed subgradient method, Jacobi and Gauss-Seidel iterations, and implication of different time scales of variable updates. Then, we introduce primal, dual, indirect, partial, and hierarchical decompositions, focusing on network utility maximization problem formulations and the meanings of primal and dual decompositions in terms of network architectures. Finally, we present recent examples on: systematic search for alternative decompositions; decoupling techniques for coupled objective functions; and decoupling techniques for coupled constraint sets that are not readily decomposable.

Original languageEnglish (US)
Article number1664999
Pages (from-to)1439-1451
Number of pages13
JournalIEEE Journal on Selected Areas in Communications
Volume24
Issue number8
DOIs
StatePublished - Aug 2006

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Electrical and Electronic Engineering

Keywords

  • Congestion control
  • Cross-layer design
  • Decomposition
  • Distributed algorithm
  • Network architecture
  • Network control by pricing
  • Network utility maximization
  • Optimization
  • Power control
  • Resource allocation

Fingerprint Dive into the research topics of 'A tutorial on decomposition methods for network utility maximization'. Together they form a unique fingerprint.

  • Cite this