Duality gap estimation and polynomial time approximation for optimal spectrum management

Zhi Quan Luo, Shuzhong Zhang

Research output: Contribution to journalArticlepeer-review

41 Scopus citations


Consider a communication system whereby multiple users share a common frequency band and must choose their transmit power spectra jointly in response to physical channel conditions including the effects of interference. The goal of the users is to maximize a system-wide utility function (e.g., weighted sum-rate of all users), subject to individual power constraints. A popular approach to solve the discretized version of this nonconvex problem is by Lagrangian dual relaxation. Unfortunately the discretized spectrum management problem is NP-hard and its Lagrangian dual is in general not equivalent to the primal formulation due to a positive duality gap. In this paper, we use a convexity result of Lyapunov to estimate the size of duality gap for the discretized spectrum management problem and show that the duality gap vanishes asymptotically at the rate O(1/√N), where N is the size of the uniform discretization of the shared spectrum. If the channels are frequency flat, the duality gap estimate improves to O(1/N). Moreover, when restricted to the FDMA spectrum sharing strategies, we show that the Lagrangian dual relaxation, combined with a linear programming scheme, can generate an ε-optimal solution for the continuous formulation of the spectrum management problem in polynomial time for any ε > 0.

Original languageEnglish (US)
Pages (from-to)2675-2689
Number of pages15
JournalIEEE Transactions on Signal Processing
Issue number7
StatePublished - 2009

Bibliographical note

Funding Information:
Manuscript received July 12, 2007; accepted December 25, 2008. First published March 10, 2009; current version published June 17, 2009. The associate editor coordinating the review of this paper and approving it for publication was Dr. Alper Tunga Erdogan. The work of Z.-Q. Luo was supported in part by the U.S. NSF, Grant CMMI 0802022 and in part by the USDOD ARMY, Grant W911NF-05-1-0567. The work of S. Zhang was supported by the Hong Kong RGC Earmarked Grants CUHK419208 and CUHK418406.


  • Cognitive radio
  • Complexity
  • Duality
  • Spectrum management
  • Sum-rate maximization
  • ε-approximation


Dive into the research topics of 'Duality gap estimation and polynomial time approximation for optimal spectrum management'. Together they form a unique fingerprint.

Cite this