A Darmstadt Frankfurt Afternoon on Optimization

June 10, 2016, 16:00 s.t.

TU Darmstadt

Dolivostr. 15, Room 1


To the main page of the meeting.

Abstracts:

Didier Henrion (LAAS-CNRS Toulouse): Optimal Experimental Design with Polynomial Optimization

Optimal experimental design consists of choosing measurements to maximize the information or, equivalently, minimize noise. For linear regression, a popular criterion is D-optimality, which seeks to maximize the determinant of the information matrix. Maximization is with respect to the weights of a discrete measure whose atoms (measurement basis vectors) are given a priori. The information matrix contains moments of degree two of this measure, and its inverse is the error covariance matrix. The resulting determinant maximization problem was one of the target applications motivating the development of semidefinite programming in the mid 1990s.

In the light of recent advances in polynomial optimization and moment-sum-of-squares relaxations, we revisit the optimal experimental design problem and extend these results on the one hand from linear to polynomial regression,and on the other hand from discrete measures with a priori given atoms to arbitrary probability measures on general semialgebraic sets. Numerical experiments reveal that sparse D-optimal atomic measures can be constructed easily e.g. for quadratic or cubic regressions on the three-dimensional sphere.

This is joint work with Yohann de Castro, Fabrice Gamboa and Jean Bernard Lasserre.


Jens Vygen (Universität Bonn): Resource Sharing, Routing, Chip Design

Chip design is one of the most fascinating application areas of mathematics. One important task is routing. Interconnecting millions of sets of pins by wires is challenging because of the huge instance sizes and limited resources. The graphs can have billions of vertices. The space for laying out the wires and the time for propagating signals along wires are very limited. Moreover, even the simplest special cases of the routing problem are NP-hard.

We show how to model the routing problem by min-max resource sharing. This includes a novel way of modeling timing constraints. We present a simple combinatorial fully polynomial approximation scheme which is both faster and more general than all previous algorithms.

We implemented the algorithm; it is used for routing the most complex chips in industry. Huge resource sharing instances are solved nearly optimally in less than an hour. The overall routing solution is far superior to those computed by industrial routing tools.