Christoph Helmberg - Konrad-Zuse-Zentrum für Informationstechnik Berlin

Semidefinite Optimierung

Abstract: Interpretiert man die zulässigen Mengen der linearen Optimierung als Schnitt eines affinen Unterraums (Ax=b) mit dem Kegel der nichtnegativen Vektoren (x >= 0), bietet es sich an, an Stelle des positiven Orthanten auch andere konvexe Kegel zu betrachten. Im Spezialfall des Kegels der symmetrischen positiv semidefiniten Matrizen (x beschreibt das obere Dreieck einer positiv semidefiniten Matrix) spricht man von semidefiniter Optimierung. Die Problemklasse stellt sich als sehr allgemein heraus, sie beinhaltet zum Beispiel lineare und konvex quadratische Optimierung sowie Eigenwertoptimierung für affine Matrixfunktionen. Entsprechend breit gestreut sind die Anwendungen, aber auch die algorithmischen Ansätze zur Lösung semidefiniter Programme. In diesem Vortrag führe ich in die Theorie der Semidefiniten Optimierung ein und gebe einen Überblick über aktuelle Lösungsverfahren.

Colloquium - 16 Uhr s.t.

Andreas Eisenblätter -Konrad-Zuse-Zentrum für Informationstechnik Berlin

k-Partitionierung: semidefinite Schranken für ein Frequenzplanungsproblem

Abstract: In der Literatur werden zahlreiche Versionen von Frequenzplanungsproblemen studiert. Bei GSM Mobilfunknetzen besteht das Ziel der Frequenzplanung häufig in der Minimierung der Gesamtinterferenz. Mathematisch lässt sich dieses Problem wie folgt fassen:

Gegeben sind ein ungerichteter Graph (V, E), ein (endliches) Intervall C in den natürlichen Zahlen, für jeden Knoten v in V eine (möglicherweise leere) Teilmenge B_v von C, sowie drei Kantenbeschriftungen d : E -> {0,...,4}, c^co:E -> [0,2] und c^ad: E -> [0,2]. Die Knoten des Graphen repräsentieren die stationären Sendestationen, C das zur Verfügung stehende Spektrum, die Mengen B_v lokale Frequenzverbote, d die notwendigen `Separationsabstände', und schliesslich c^co sowie c^ad gegebenenfalls auftretende Gleich- bzw. Nachbarkanalinterferenz.

Eine (Frequenz-)Zuweisung y :V -> C heisst zulässig falls y(v) notin B_v für alle v in V und | y(v) -y(w)|>=d(vw) für alle vw in E gilt. Das Ziel der Planung besteht im Auffinden einer zulässigen Zuweisung y, welche die Gesamtinterferenz
Summe c^co(vw) über alle vw in E mit y(v)=y(w) + Summe c^ad(vw) über alle vw in E mit |y(v) - y(w)|=1
minimiert.

Mehrere ILP Formulierungen dieses Problems sind bekannt. Doch konnte bisher keine davon erfolgreich zur Herleitung unterer Schranken für die Gesamtinterferenz bei praxisrelevanten Daten eingesetzt werden.

In diesem Vortrag wird das genannte Frequenzzuweisungsproblem vereinfacht zu einem k-Partitionierungsproblem auf Graphen. Dies geschieht durch das Vernachlässigen der lokalen Frequenzverbote (B_v = emptyset für alle v in V), das Reduzieren der Separationsgebote in d auf höchstens 1 und das Vernachlässigen der Nachbarkanalinterferenz (c^ad = 0).

Aus dem vereinfachten Problem lä{\ss}t sich eine semidefinite Relaxierung herleiten. Die numerische Lösung dieser Relaxierung liefert untere Schranken für die Gesamtinterferenz des Ausgangsproblems. Die auf diese Weise erhaltenen Schranken übertreffen alle bisherigen Resultate deutlich.