Group for Research in Decision Analysis

Non-convexity Issues in Optimal Resource Allocation in Wireless Networks

Ravi Mazumdar Department of Electrical and Computer Engineering, University of Waterloo, Canada

This talk will focus on the problem of resource allocation and scheduling in wireless networks. In this context the inherent utility functions are non-concave. However, the current network optimization algorithms deal are only suited for the concave case. The non-convexity results in a duality gap and the fact that the KKT conditions do not hold. In the talk I will discuss the consequences of non-convexity in designing distributed schemes. In particular, I will discuss the problem of joint power and rate allocation as well as the issues of scheduling multiple users that we term power scheduling focussing on the downlink.

In the first part we will show how a good distributed algorithm can be developed and that the framework also provides us with the means of studying the optimality of scheduling (single user TDMA type) VS multi-user (CDMA type) policies.

In the second part we will show how to solve a general multi-user scheduling problem when utilities are non-convex. By exploiting the framework of sub-differentials we show simple, distributed algorithms can be developed that yield substantial performance improvements while assuring some degree of fairness.