First-order algorithms for nonsmooth nonconvex optimization in large-scale wireless networks

Abstract

To meet the dramatically increasing demand for higher data rate and larger numbers of connections, wireless networks are becoming larger and larger, which manifests in the numbers of antennas, base stations (BSs), and Internet-of-Things (IoT) devices. Scaling up the wireless systems provides a bright prospect in terms of performance improvement, but it also brings new challenges to optimization problems in algorithm design. Mathematically, many resource allocation and signal processing problems in modern wireless networks belong to the class of large-scale nonsmooth nonconvex optimization problems. While second-order algorithms, which involve both the gradient vector and the Hessian matrix, have been widely applied to nonsmooth and nonconvex problems in small-scale or medium-scale wireless networks, their cubic-order complexity burden makes them inapplicable to large-scale problems with large numbers of variables. For instance, in a large-scale wireless network, where 50 multicast groups of users are served by 50 four-antenna BSs, the dimension of multicast beamforming variables is 10^4, and thus the complexity order of second-order algorithms would be 10^12. In contrast, first-order algorithms need only gradient information and hence enjoy much lower complexity, making them indispensable for large-scale optimization problems. However, first-order algorithms are mostly designed for simply convex problems, whereas most resource allocation and signal processing problems in wireless networks are nonsmooth and nonconvex (e.g., multicast beamforming design and BS clustering). Furthermore, these well-established first-order algorithms (e.g., alternating direction method of multipliers) can only guarantee the convergence for convex setting under mild conditions. Therefore, it is still a challenge to develop appropriate first-order algorithms with convergence guarantees for the large-scale nonsmooth nonconvex problems appearing in large-scale wireless networks. Despite the challenges, this thesis develops customized first-order algorithms with convergence guarantees for different large-scale wireless networks. In particular, this thesis proposes first-order algorithms for 1) energy-efficient precoding design under non-orthogonal multicast and unicast transmission in a massive multiple-input multiple-output system; 2) sparse multicast beamforming design in a large-scale cloud radio access network; 3) activity detection under frequency offsets in massive IoT. Since the proposed first-order algorithms involve only gradient information, they require much shorter computation time than the second-order based approaches, but still achieve the same performance. Furthermore, the proposed algorithms are proved to converge to critical points even for the considered nonsmooth nonconvex problems. This is in sharp contrast to the existing first-order and second-order algorithms, making the proposed algorithms indispensable for large-scale wireless networks with hundreds or thousands of antennas/BSs/users.