An overview of 1 year research!

Greetings, and welcome to 2021! 😀💪 As we embark upon a new year, we are excited to set new goals and reflect upon the progress made in research during the past year.

Over the course of the project's initial months, we have dedicated ourselves to exploring the concept of generalized Augmented Lagrangians for the solution of semidefinite programs, with a particular emphasis on the structures and difficulties that arise in the context of polynomial optimization. Two main aspects of our research have thus far been taken into account: ill-conditioning and a low-rank structure in the data.

To address the ill-conditioning problem, we have proposed a general class of barrier functions, known as penalty-barrier-functions, which provide an upper bound for the eigenvalues of the Hessian of the Augmented Lagrangian. Although this approach has been reported in the literature previously, our project combines it with a regularization technique, providing a uniform lower bound for the eigenvalues.

One of the main challenges associated with using penalty-barrier-functions in semidefinite programming is that the computational complexity of assembling the Hessian matrix is an order of magnitude higher than that of comparable approaches using modified barrier functions or the well-known log det-function as used in interior-point methods. To overcome this challenge, we have demonstrated that combining the Penalty-Barrier-Concept with iterative solution methods for the solution of arising Newton-type systems can eliminate this disadvantage. This is particularly relevant for polynomial optimization problems, where tight approximations often lead to large SDPs that can be computationally demanding to solve.

Despite the challenges posed by Covid-19 and the associated restrictions, we are pleased to report that ESR13 (Soodeh) from the University of Birmingham and I were both able to complete our secondments. During ESR13's research stay at FAU, we collaborated in person, sharing an office at FAU and organizing regular meetings between our two universities (approximately biweekly). During these meetings, we exchanged ideas with each other and our advisors on developing optimization solvers that take structures specific to polynomial optimization problems into account. This includes a common data and software basis maintained by the two groups. Our focus thus far has been on identifying common structures in interior-point methods and primal-dual methods based on Augmented Lagrangians, with the aim of developing iterative methods and preconditioners that can be applied in the framework of both solution concepts. We have tested these methods using problems from truss topology design.

Moving forward, we plan to extend our scope to more general polynomial optimization problems and continue working on preconditioners that can help cope with the high computational complexity expected for significant polynomial optimization problems provided by our partners in the future.