T-3: Efficient Global Optimization and its Application to Wireless Interference Networks: Part 1: Introduction

Global optimization is concerned with obtaining the solution of nonconvex optimization problems. Algorithms for such problems can mostly be categorized into outer approximation algorithms and branch and bound (BB) methods. This tutorial will focus on BB methods for continuous optimization and demonstrate that they are one of the most versatile tools in global optimization theory. We take a modular approach to BB and cover the aspects of rectangular subdivision, selection, bounding, and feasibility testing, both, from a theoretical and practical perspective. The focus for the bounding part is on exploiting partial monotonicity in the problem, which leads to the novel mixed monotonic programming (MMP) framework, a generalization of classical monotonic optimization (MO). Common feasibility checks are discussed and we highlight some pitfalls that lead to slow convergence speeds. The successive incumbent transcending (SIT) scheme is introduced as a remedy and its integration with BB is discussed. A notable side effect of this SIT scheme is that it also improves numerical stability when dealing with complicated feasible sets. The theory developed in the first part of this tutorial will be applied in several case studies from the area of resource allocation for wireless interference networks.