Algorithms for Homogeneous Quadratic Minimization And Applications in Wireless Networks

Abstract

Massive proliferation of wireless devices throughout world in the past decade comes with a host of tough and demanding design problems. Noise at receivers and wireless interference are the two major issues which severely limits the received signal quality and the quantity of users that can be simultaneously served. Traditional approaches to this problems are known as Power Control (PC), SINR Balancing (SINRB) and User Selection (US) in Wireless Networks respectively. Interestingly, for a large class of wireless system models, both this problems have a generic form. Thus any approach to this generic optimization problem benefits the transceiver design of all the underlying wireless models. In this thesis, we propose an Eigen approach based on the Joint Numerical Range (JNR) of hermitian matrices for PC, SINRB and US problems for a class of wireless models.

In the beginning of the thesis, we address the PC and SINRB problems. PC problems can be expressed as Homogeneous Quadratic Constrained Quadratic Optimization Problems (HQCQP) which are known to be NP-Hard in general. Leveraging their connection to JNR, we show that when the constraints are fewer, HQCQP problems admit iterative schemes which are considerably fast compared to the state of the art and have guarantees of global convergence. In the general case for any number of constraints, we show that the true solution can be bounded above and below by two convex optimization problems. Our numerical simulations suggested that the bounds are tight in almost all scenarios suggesting the achievement of true solution. Further, the SINRB problems are shown to be intimately related to PC problems, and thus share the same approach. We then proceed on to comment on the convexity of PC problems and SINRB problems in the general case of any number of constraints. We show that they are intimately related to the convexity of joint numerical range. Based on this connection, we derive results on the attainability of solution and comment on the same about the state-of-the-art technique Semi-De nite Relaxation (SDR).

In the subsequent part of the thesis, we address the US problem. We show that the US problem can be formulated as a combinatorial problem of selecting a feasible subset of quadratic constraints. We propose two approaches to the US problem. The first approach is based on the JNR view point which allows us to propose a heuristic approach. The heuristic approach is then shown to be equivalent to a convex optimization problem. In the second approach, we show that the US is equivalent to another non-convex optimization problem. We then propose a convex approximation approach to the latter. Both the approaches are shown to have near optimal performance in simulations.

We conclude the thesis with a discussion on applicability and extension to other class of optimization problems and some open problems which has come out of this work.