Non-Asymptotic Bounds on the Performance of Dual Methods for Resource Allocation Problems


S. Görtzen, A. Schmeink,


        In this paper, dual methods based on Lagrangian relaxation for multiuser multicarrier resource allocation problems are analyzed. Their application to non-convex resource allocation problems is based on results guaranteeing asymptotic optimality as the number of subcarriers tends to infinity. This work analyzes the workings and performance of dual methods for resource allocation problems with concave rate functions and a finite number of subcarriers. The core results are the convexity of resource allocation problems with subcarrier sharing and an upper bound on the number of subcarriers being shared. Based on these results, absolute and relative performance bounds are presented for dual methods when applied to the resource allocation problem without subcarrier sharing. The exemplary problems considered in this work are sum rate maximization with global and individual power budgets and sum power minimization with global and individual rate demands.

keywords={Minimization;Optimization;Performance evaluation;Power demand;Resource management;Upper bound;Wireless communication;Resource allocation;adaptive modulation;combinatorial optimization;convex optimization;duality theory;orthogonal frequency division multiple access (OFDMA)} ISSN={1536-1276}

BibTEX Reference Entry 

	author = {Simon G{\"o}rtzen and Anke Schmeink},
	title = "Non-Asymptotic Bounds on the Performance of Dual Methods for Resource Allocation Problems",
	pages = "3430-3441",
	journal = "{IEEE} Transactions on Wireless Communications",
	volume = "13",
	number = "6",
	doi = 10.1109/TWC.051414.131480,
	month = Jun,
	year = 2014,
	hsb = hsb999910346799,


 Download paper  Download bibtex-file

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights there in are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.