Non-convexity issues in optimal resource allocation in wireline and wireless networks

Ravi Mazumdar

Purdue University, USA


In this talk we will discuss the problem of implementing a distributed scheme for allocating bandwidth and power for optimizing total system performance in wireline and wireless networks with QoS requirements. This results in the non-convexity of user utility functions. However, the current network optimization algorithms deal with only the convex case. The non-convexity results in the filure of the Karush-Kuhn-Tucker conditions to identify the necessary conditions as well as non-differentiability of the dual. This has important implications in the design of distributed algorithms, for example the lack of stability which can lead to congestion. In the talk I will discuss the consequences of non-convexity in designing distributed schemes. The algorithms depend on the degree of co-ordination that is possible and thus the implementations will differ for the wireless and wireline cases. In a solution more appropriate for the wireless context, we show that a pricing based mechanism in the dual formulation can be developed. For the wireline case, an algorithm based on the theory of sub-differentials with a "self-regulatory" property that influences the users to access the resource or not based on the net utility is proposed. We discuss the convergence issues and show that the algorithms can be efficient in the sense of achieving the social optimal when ther are many small users.

[Ravi Mazumdar]
[Purdue University, USA]