Mixed Monotonic Programming for Fast Global Optimization

Abstract

While globally optimal solutions to many convex programs can be computed efficiently in polynomial time, this is, in general, not possible for nonconvex optimization problems. Therefore, locally optimal approaches or other efficient suboptimal heuristics are usually applied for practical implementations. However, there is also a strong interest in computing globally optimal solutions of nonconvex problems in offline simulations in order to benchmark the faster suboptimal algorithms. Global solutions often rely on monotonicity properties. A common approach is to reformulate problems into a canonical monotonic optimization problem where the monotonicity becomes evident, but this often comes at the cost of nested optimizations, increased numbers of variables, and/or slow convergence. The framework of mixed monotonic programming (MMP) proposed in this paper avoids such performance-deteriorating reformulations by revealing hidden monotonicity properties directly in the original problem formulation. By means of a wide range of application examples from the area of signal processing for communications (including energy efficiency for green communications, resource allocation in interference networks, scheduling for fairness and quality of service, as well as beamformer design in multiantenna systems), we demonstrate that the novel MMP approach leads to tremendous complexity reductions compared to state-of-the-art methods for global optimization. However, the framework is not limited to optimizing communication systems, and we expect that similar speed-ups can be obtained for optimization problems from other areas of research as well.

submitted to IEEE Transactions on Signal Processing; Source code available at https://github.com/bmatthiesen/mixed-monotonic

References in corpus (10)

• Energy-Efficient Power Control: A Look at 5G Wireless Technologies
• Globally Optimal Energy-Efficient Power Control and Receiver Design in Wireless Networks
• Optimal Linear Precoding Strategies for Wideband Non-Cooperative Systems based on Game Theory-Part II: Algorithms
• Robust Monotonic Optimization Framework for Multicell MISO Systems
• Achieving Global Optimality for Weighted Sum-Rate Maximization in the K-User Gaussian Interference Channel with Multiple Antennas
• A Unified Successive Pseudo-Convex Approximation Framework
• Resource Allocation for Energy-Efficient 3-Way Relay Channels
• Efficient Global Optimal Resource Allocation in Non-Orthogonal Interference Networks
• Optimization of Weighted Individual Energy Efficiencies in Interference Network
• Improper Signaling versus Time-Sharing in the Two-User Gaussian Interference Channel with TIN

Cited by in corpus (5)

• A Globally Optimal Energy-Efficient Power Control Framework and its Efficient Implementation in Wireless Interference Networks
• Globally Optimal Spectrum- and Energy-Efficient Beamforming for Rate Splitting Multiple Access
• Optimal Resource Allocation for Multi-user OFDMA-URLLC MEC Systems
• Two-User SIMO Interference Channel with TIN: Improper Signaling versus Time-Sharing
• Resource Allocation for Simultaneous Wireless Information and Power Transfer Systems: A Tutorial Overview