A Frankfurt-Darmstadt Afternoon on Optimization

June 22, 2018, 16:00 s.t.

Goethe-Universität Frankfurt am Main, Campus Bockenheim

Robert-Mayer-Str. 10, Room (tba)

To the main page of the meeting


Michael Joswig (TU Berlin): Linear Programming Seen Through Tropical Geometry

We will give a basic introduction on how tropical geometry is relevant for questions concerning algorithmic complexity in optimization. Specifically, we will see that primal-dual log-barrier interior point methods for linear programming are not strongly polynomial. This result is established by constructing a family of linear programs with 3r+1 inequalities in dimension 2r for which the number of iterations lies in Ω(2^r). Our method is to tropicalize the central path in linear programming. The tropical central path is the piecewise-linear limit of the central paths of parameterized families of classical linear programs viewed through logarithmic glasses. This is joint work with Xavier Allamigeon, Pascal Benchimol and Stéphane Gaubert.

Oliver Stein (Karlsruhe Institute of Technology): Interrelations between Disjunctive and Generalized Semi-infinite Programming

In generalized semi-infinite programs (GSIPs) a finite dimensional decision variable is subject to infinitely many inequality constraints whose index set may depend on the decision variable. Applications comprise design centering, robust optimization, and minimax problems. Due to an inherent disjunctive structure of GSIPs, disjunctive programming is not only another interesting field for their application but, in turn, techniques from disjunctive optimization are also beneficial for the solution of GSIPs. In fact, in a first part of the talk we describe a possibility to model disjunctive optimization problems as GSIPs and to solve them locally by standard methods from nonlinear optimization. In a second part we propose a new branch-and-bound algorithm for the global minimization of box-constrained GSIPs. It treats the inherent disjunctive structure of these problems by tailored lower bounding procedures. We present numerical results as proof of concept for both approaches.