A Darmstadt-Frankfurt Afternoon
on Optimization

July 5, 2019

A Darmstadt-Frankfurt Afternoon on Optimization

July 5, 2019, 16:00 s.t.

TU Darmstadt

Dolivostr. 15, Room 1

To the main page of the meeting.

Abstracts:

Stefan Weltge (TU München): Stable sets and odd cycles

The stable set problem is among the most famous combinatorial optimization problems. While it is NP-hard in general graphs, we consider the class of graphs with no k disjoint odd cycles, where k is any constant. It is an open problem whether the stable set problem is polynomially solvable in such graphs. In this talk, we will report about recent progress on this problem and demonstrate that its study requires a fascinating machinery from fields as integer programming, structural graph theory, and topology. This is based on joint work with Samuel Fiorini, Michele Conforti, Gwenaël Joret, and Tony Huynh.

Florian Jarre (Universität Düsseldorf): Stochastic gradient descent and Block coordinate descent - an introduction to the theory and a practical application

The talk addresses extremely high-dimensional minimization problems of special structure. Even the evaluation of a single function value demands so much computation time that new iterative methods are applied for which a single iteration is cheaper than a single function evaluation. Of course, one cannot expect proofs of rapid convergence when one cannot even afford function evaluations. Nevertheless, in this talk we outline a simple proof of convergence of the expected values of stochastic gradient descent and of block coordinate descent methods, illustrate the relation between both approaches and discuss possible modifications for practical implementations.