Utility maximization and algorithms in software-defined radio networks by nonlinear Perron-Frobenius theory

Abstract

Network optimization is important in the design of next-generation communication networks, especially for utility maximization and resource allocation. In addition, the rapid growth of both mobile computing services and data traffic require new distributed algorithms that are scalable and optimal for the ease of distributed and low-complexity implementation. A notorious hurdle in utility maximization of software-defined radio networks is the nonlinearity and non-convexity. For example, sum rate maximization is proved to be NP-hard; and max-min utility fairness optimization comes in various forms due to many nonlinear link metrics. In this dissertation, we develop a nonlinear Perron-Frobenius theoretic framework to tackle the non-convexity barriers in software-defined radio network utility maximization. We first present a unified framework to solve a class of max-min utility fairness optimization problems with generalized monotonic constraints. By applying the nonlinear Perron-Frobenius theory, the optimal value and solution of these problems can be characterized analytically by solutions of conditional eigenvalue problems with concave positive mappings. It provides a systematic way to derive distributed and fast-convergent algorithms and to evaluate the fairness of resource allocation. This approach also advances the state-of-the-art in handling nonlinear monotonic constraints. Several representative applications are considered to illustrate the effectiveness of the proposed framework. We then apply the nonlinear Perron-Frobenius theory to more general utility maximization problems. Closed-form solution can be obtained involving spectral radius of specially crafted nonnegative matrices. As by-products, new insights can be drawn, for instances, the development of network duality that can be leveraged to decouple power and interference temperature, interesting optimality equivalences between different problems and polynomial-time solvability of nonconvex special cases. In particular, we propose a reformulation-relaxation technique for sum rate maximization that provides a useful upper bound to the optimal value and enables global optimization algorithms by utilizing branch-and-bound method.

Date of Award	15 Jul 2015
Original language	English
Awarding Institution	City University of Hong Kong
Supervisor	Chee Wei TAN (Supervisor)