Optimal Resource Allocation for Wireless Communications: Complexity Analysis and Algorithm Design

Resource allocation is a fundamental problem in the design of wireless communication systems. The mutual interference among users, which is a major factor of limiting the performance of communication systems, can be effectively mitigated by carefully allocating wireless resources such as transmission power, transmission waveforms, and frequency bands. Most of the resource allocation problems arising from wireless communications can be formulated as optimization problems. On one hand, these optimization problems are often non-convex and highly nonlinear; on the other hand, these problems have their own special structures such as hidden convexity and separability. In this talk, we shall focus on two resource allocation problems, especially on characterizing the computational complexity of these problems, and designing customized algorithms for solving these problems by the use of their special structures.  

In the first part, we talk about the max-min fairness linear transceiver design problem for a multi-user multi-input multi-output (MIMO) interference channel. This problem can be formulated as the maximization of the minimum signal to interference plus noise ratio (SINR) utility, subject to individual power constraints at each transmitter. We prove that, if the number of antennas is at least two at each transmitter (receiver) and is at least three at each receiver (transmitter), the max-min fairness linear transceiver design problem is computationally intractable as the number of users becomes large. We then propose two iterative algorithms to solve the max-min fairness linear transceiver design problem. The transceivers generated by these algorithms monotonically improve the min-rate utility and are guaranteed to converge to a stationary solution.  

In the second part, we talk about the joint power and admission control (JPAC) problem for a multi-user single-input single-output (SISO) interference channel. The goal is to support a maximum number of links at their specified SINR targets while using minimum total transmission power. Various convex approximation deflation approaches have been developed for the JPAC problem. We propose an effective polynomial time non-convex approximation deflation approach for solving the problem. The proposed approach is based on the non-convex $ell_q (0<q<1)$ approximation of an equivalent sparse $ell_0$ reformulation of the JPAC problem. Numerical simulations show that the proposed approach significantly outperforms the existing convex approximation approaches in terms of the number of supported links and the total transmission power, particularly exhibiting a quite good performance in selecting which subset of links to support.