Semidefinite Programmierung

In der Semidefiniten Programmierung (SDP, auch Semidefinite Optimierung) werden Optimierungsprobleme untersucht, deren Variablen keine Vektoren, sondern symmetrische Matrizen sind. Als Nebenbedingung wird verlangt, dass diese Matrizen positiv (oder negativ) semidefinit sind, woraus sich der Name der Problemstellung ergibt.

Die Zielfunktion ist in vielen Fällen linear, sodass sich die Semidefinite Programmierung als Erweiterung der Linearen Optimierung auffassen lässt. Sie kann aber auch nichtlinear sein.

Da die Menge aller positiv semidefiniten Matrizen im Vektorraum der symmetrischen Matrizen ein Kegel (engl. cone) ist, kann man die Semidefinite Programmierung als Teilgebiet der conic optimization bezeichnen.

Anwendungen gibt es auf dem Gebiet der konvexen Optimierung, der Approximationstheorie, der Kontrolltheorie, der kombinatorischen Optimierung und auch in der Technik.

Problemformulierung

Im linearen Fall lautet die Standardformulierung für ein Problem der Semidefiniten Programmierung:

$\min \mathrm{tr}\ (CX)\$

unter den Nebenbedingungen

$\mathrm{tr}\ (A_i X) = b_i,\quad i=1,\dots,p$

$X \succeq0$

wobei die Matrizen $C,A_1 ,\dots,A_p \in S_n$ und die Werte $b_i \in \mathbb{R}$ fest vorgegeben sind. Die Variable X ist ebenfalls eine Matrix. $X \succeq0$ bedeutet, dass die Matrix X positiv semidefinit sein soll. tr steht als Abkürzung für die Spur (engl. trace) der Matrix. S_n ist die Menge der symmetrischen ${n\times n}$ -Matrizen

Beispiel

Will man eine symmetrische Matrix finden, für die die Summe der k größten Eigenwerte so klein wie möglich ist, kann man das als Problem der semidefiniten Programmierung formulieren. Dabei minimiert man als Zielfunktion die Variable t, von der man in einer Nebenbedingung fordert, dass sie größer oder gleich der Summe der k größten Eigenwerte von X ist. Diese Nebenbedingung ist sehr schwierig zu handhaben, weil es keine leicht zu berechnende Funktion gibt, die zu einer Matrix die Eigenwerte angibt, schon gar nicht in einer sortierten Form. Allerdings kann man die Nebenbedingung äquivalent durch die folgenden drei Bedingungen ausdrücken:^[1]

1. $t-ks-\mathrm{tr}(Z)\geq 0$
2. $Z\succeq 0$
3. $Z-X+sE \succeq 0$.

Dabei ist E die Einheitsmatrix, t und s sind reelle Variablen, X und Z sind Matrixvariablen. Diese Bedingungen sind mathematisch leichter zu behandeln, obwohl sie auf den ersten Blick schwieriger aussehen. Alle lassen sich einfach berechnen, da sie linear in den Variablen sind. Auch die Berechnung der Spur ist einfach. Für die Überprüfung auf positive Semidefinitheit für die zweite und dritte Bedingung gibt es spezielle Verfahren, die dann zur Lösung des Problems herangezogen werden.

Literatur

• Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2004, ISBN 3-540-43575-1.
• Johannes Jahn: Introduction to the Theory of Nonlinear Optimization. 3. Auflage. Springer, Berlin 2007, ISBN 978-3-540-49378-5.

Einzelnachweise

1. ↑ Florian Jarre, Josef Stoer: Optimierung. Springer, Berlin 2004, S. 419.

Weblinks

• Christoph Helmberg: Seite mit vielen weiterführenden Links (englisch). Abgerufen am 19. Juli 2008.