Mixed Monotonic Programming for Fast Global Optimization
share
While globally optimal solutions to 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 form of a 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 is a more direct approach that exploits hidden monotonicity properties without performance-deteriorating reformulations. 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.
READ FULL TEXT