Tutorial #7 – Efficient Global Optimization

Instructor: Bho Matthiesen, University of Bremen, Germany
Instructor: Eduard A. Jorswieck, Technische Universität Braunschweig, Institut für Nachrichtentechnik, Germany

Abstract: Global optimization is concerned with obtaining the globally optimal 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 procedures 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. In particular, we will cover energy-efficient resource allocation and show how to approach such problems without Dinkelbach’s algorithm. Further applications are hierarchical resource allocation, beamforming, and resource allocation over rate regions. Although all of these problems are NP-hard we will demonstrate that they can be solved efficiently for small to medium scale problems.

Bio: Bho Matthiesen received the Diplom-Ingenieur (M.Sc.) degree and his Ph.D. degree (with distinction) from Technische Universität Dresden, Germany, in 2012 and 2019, respectively. From 2012 to 2019, he has been a Research Associate with the Chair of Communications Theory, Technische Universität Dresden. Since 2020, he is a research group leader at the U Bremen Excellence Chair of Petar Popovski in the Department of Communications Engineering, University of Bremen, Germany. His research interests are in the area of signal processing for communications, with a focus on optimization methods for resource allocation. He was an invited speaker at the 2nd 6G Wireless Summit and is a publication chair for the International Symposium on Wireless Communication Systems (ISWCS) 2020.

Bio: Eduard A. Jorswieck was born in 1975 in Berlin, Germany. Since August 2019, he has been the head of the Chair for Communications Systems and Full Professor at Technische Universität Braunschweig, Germany. From 2008 until 2019, he was the head of the Chair of Communications Theory and Full Professor at Dresden University of Technology (TUD), Germany. His main research interests are in the broad area of communications. He has published more than 110 journal papers, 13 book chapters, 3 monographs, and some 275 conference papers on these topics.
Dr. Jorswieck is an IEEE Fellow and member of the IEEE SAM Technical Committee since 2015. Since 2017, he serves as Editor-in-Chief of the EURASIP Journal on Wireless Communications and Networking. He serves currently on the editorial board for IEEE Transactions on Information Forensics and Security. In 2006, he received the IEEE Signal Processing Society Best Paper Award.