M/614

Relaxierungen spielen eine entscheidende Rolle, wenn ein diskretes Optimierungsproblem (etwa mit Branch-and-Bound) gelöst werden soll. Neben der bekannten LP-Relaxierung sind in den letzten Jahren vermehrt so genannte semidefinite Relaxierungen betrachtet worden. Das urspr¨ungliche Problem wird dabei in einen h¨oherdimensionalen Raum von Matrixvariablen transformiert, wobei die Ganzzahligkeitsbedingungen mittels spezieller Matrixbedingungen relaxiert werden: es wird verlangt, dass die Matrixvariable im Kegel der positiv semidefiniten Matrizen enthalten sei. Für solche semidefinite Programme gibt es sehr effiziente Algorithmen. Die Lösung erfordert zwar einen etwas höheren Rechenaufwand als die Berechnung der LP-Relaxierung, qualitativ ist die semidefinite Relaxierung der LP-Relaxierung aber oft deutlich ¨uberlegen. Noch bessere Schranken (in manchen F¨ allen sogar die Optimall¨osung) lassen sich berechnen, indem man statt des Kegels der semidefiniten Matrizen andere konvexe Kegel, zum Beispiel den Kegel der so genannten copositiven Matrizen betrachtet. Im Vortrag sollen Vor- und Nachteile dieser Relaxierungstechniken diskutiert werden. Insbesondere wird ein neues Approximationsschema vorgestellt, mit Hilfe dessen copositive Programme bis auf eine vorgegebene Genauigkeit gelöst werden können. Der Ansatz beruht auf polyedrischen Approximationen des copositiven Kegels sowohl von innen als auch von außen. Ersetzt man den copositiven Kegel durch diese approximierenden Kegel, so erhält man ein lineares Problem, das effizient gelöst werden kann. Durch geschickte Verfeinerung der Approximation erzeugt man eine Folge von LPs, die das vorgegebene copositive Programm beliebig genau approximieren. Dabei kann die Verfeinerung so gesteuert werden, dass nur in dem für die Optimierung relevanten Bereich verfeinert wird und der numerische Aufwand begrenzt bleibt. Die Resultate zur Copositiven Optimierung sind in Zusammenarbeit mit Stefan Bundfuss entstanden.

Tee 15:45 Uhr im Raum M/614

Prof. Dr. Mirjam Dür

Technische Universität Darmstadt