Efficient Storage Layouts for Nonconvex Optimization Procedures

Tutor: Bho Matthiesen
Type of Thesis: Project (MSc), Bachelor thesis (BSc.)
date of issue: -
Student: -
Status: available

Optimization theory is an essential tool in the design of communication systems and signal processing algorithms. While convex optimization problems can be solved efficiently even for a very large number of variables, nonconvex programs are often NP-hard and have exponential computational complexity. However, efficient algorithms can be designed that are able to solve small and medium scale problems with guaranteed optimality. Given that many engineering problems are inherently nonconvex, global optimization theory is an important tool to verify heuristic algorithms and to obtain authoritative performance assessments.

A widely employed algorithmic approach to solve such problems is known as branch-and-bound. Combined with mixed monotnoic programming [1], this algorithm can solve power allocation problems in interference networks quite efficiently. Numerical experiments show that the current performance bottleneck in the solution of these problems is the memory consumption of the algorithm. The goal of this thesis is to reorganize the storage layout in a tree-like fashion to improve the memory efficiency and allow the solution of larger problem instances.

This requires a good command of C++. Knowledge in optimization theory and in communication systems is favorable but not strictly required. The thesis can be written in English or German.

[1] B. Matthiesen, C. Hellings, E. A. Jorswieck, and W. Utschick, “Mixed monotonic programming for fast global optimization”, IEEE Transactions on Signal Processing, vol. 68, pp. 2529–2544, Mar. 2020.

Last change on 17.11.2020 by B. Matthiesen
AIT ieee GOC tzi ith Fachbereich 1
© Department of Communications Engineering - University of BremenImprint / Contact