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

Prof. Ya-Feng LIU
Institute of Comptational Mathematics and Scientific/Engineering Computing, Beijing, China
Wednesday, 22 October, 2014
11:00am - 12:00pm
Room 833, Ho Sin Hang Engineering Building, The Chinese University of Hong Kong

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.





Ya-Feng Liu (M’12) received the B.Sc. degree in applied mathematics in 2007 from Xidian University, Xi'an, China, and the Ph.D. degree in computational mathematics in 2012 from the Chinese Academy of Sciences (CAS), Beijing, China. During his Ph.D. study, he was supported by the Academy of Mathematics and Systems Science, CAS, to visit Professor Zhi-Quan (Tom) Luo at the University of Minnesota (Twins Cities) from February 2011 to February 2012.  

After his graduation, he joined the Institute of Computational Mathematics and Scientific/Engineering Computing, Beijing, China, in July 2012, where he is currently an Assistant Professor. His main research interests are nonlinear optimization and its applications to signal processing and wireless communications.  

Dr. Liu received the Best Paper Award from the IEEE International Conference on Communications (ICC) in 2011.