Efficient Global Optimal Resource Allocation in Non-Orthogonal Interference Networks
arXiv:1812.07253 · doi:10.1109/TSP.2019.2941068
Abstract
Many resource allocation tasks are challenging global (i.e., non-convex) optimization problems. The main issue is that the computational complexity of these problems grows exponentially in the number of variables instead of polynomially as for many convex optimization problems. However, often the non-convexity stems only from a subset of variables. Conventional global optimization frameworks like monotonic optimization or DC programming treat all variables as global variables and require complicated, problem specific decomposition approaches to exploit the convexity in some variables. To overcome this challenge, we develop an easy-to-use algorithm that inherently differentiates between convex and non-convex variables, preserving the low computational complexity in the number of convex variables. Another issue with these widely used frameworks is that they may suffer from severe numerical problems. We discuss this issue in detail and provide a clear motivating example. The solution to this problem is to replace the traditional approach of finding an ε-approximate solution by the novel concept of ε-essential feasibility. The underlying algorithmic approach is called successive incumbent transcending (SIT) algorithm and builds the foundation of our developed algorithm. A further highlight of this algorithm is that it inherently treats fractional objectives making the use of Dinkelbach's iterative algorithm obsolete. Numerical experiments show a speed-up of four orders of magnitude over state-of-the-art algorithms and almost three orders of magnitude of additional speed-up over Dinkelbach's algorithm for fractional programs.
arXiv commentsubmitted to IEEE Transactions on Signal Processing; Source code available at https://github.com/bmatthiesen/efficient-global-opt
References in corpus (11)
- Wireless Information and Power Transfer: Energy Efficiency Optimization in OFDMA Systems
- Cooperative Interference Management with MISO Beamforming
- Energy-Efficient Power Control: A Look at 5G Wireless Technologies
- Globally Optimal Energy-Efficient Power Control and Receiver Design in Wireless Networks
- Robust Monotonic Optimization Framework for Multicell MISO Systems
- Optimal Achievable Rates for Interference Networks with Random Codes
- Distributed Optimization for Coordinated Beamforming in Multi-Cell Multigroup Multicast Systems: Power Minimization and SINR Balancing
- Energy-Efficient Beam Coordination Strategies with Rate Dependent Processing Power
- Resource Allocation for Energy-Efficient 3-Way Relay Channels
- Instantaneous Relaying for the 3-Way Relay Channel with Circular Message Exchanges
- Optimization of Weighted Individual Energy Efficiencies in Interference Network