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

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.