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.

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

Problemformulierung

Gegeben sei der reelle Vektorraum der reellen, symmetrischen $n\times n$ Matrizen $S^{n}$ versehen mit dem Frobenius-Skalarprodukt

$\langle A,B\rangle _{F}=\sum _{i=1}^{n}\sum _{j=1}^{n}a_{ij}b_{ij}=\operatorname {tr} (AB)$.

Hierbei ist $\operatorname {tr}$ die Spur einer Matrix.

Des Weiteren sei $S_{+}^{n}$ der Kegel der symmetrischen, positiv semidefiniten Matrizen und $\preccurlyeq _{S_{+}^{n}}$ die durch diesen Kegel definierte verallgemeinerte Ungleichung.

Dann heißt das Optimierungsproblem

${\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{F}&\\{\text{unter den Nebenbedingungen }}&X\succcurlyeq _{S_{+}^{n}}0&\,{\text{(positiv semidefinitheit)}}\\&\langle {A_{i}},{X}\rangle _{F}=b_{i}&\,{\text{für }}i=1,\dots ,m\end{aligned}}$

mit $C,X,A_{i}\in S^{n}$ ein lineares semidefinites Programm oder einfach semidefinites Programm (kurz SDP). Gesucht wird also eine reelle, symmetrische Matrix $X$, die positiv semidefinit ist, deren Skalarprodukt mit vorgegebenen Matrizen einen bestimmten Wert annimmt und die maximal bezüglich des Frobenius-Skalarprodukts ist. Gelegentlich werden auch nichtlineare semidefinite Programme betrachtet, diese haben dann entweder keine lineare Zielfunktion mehr oder nichtlineare Restriktionen.

Alternative Formulierungen

Die Formulierung in der Definition wird auch die Standartfprm eines SDPs genannt. Analog zu Linearen Optimierungsproblemen existiert auch die Ungleichungsform eines SDPs:

${\begin{aligned}{\text{Minimiere }}&s(x)=c^{T}x\\{\text{unter den Nebenbedingungen }}&x_{1}A_{1}+\dots +x_{m}A_{m}\preccurlyeq _{S_{+}^{n}}B\end{aligned}}$

wobei $x,c\in \mathbb {R} ^{m}$ und $A_{i},B\in S^{n}$ sind.

Klassifikation und Spezialfälle

Semidefinite Programme sind konische Programme auf dem Vektorraum der symmetrischen reellen Matrizen versehen mit dem Frobenius-Skalarprodukt und unter Verwendung des Kegels der positiv semidefiniten Matrizen. Somit sind sie ein allgemieneres konvexes Optimierungsproblem. Die Auftretenden Restriktionen sind zwar nicht immer konvex, aber auf jeden Fall K-konvex oder Linear.

Ein Spezialfall eines semidefiniten Programmes ist ein Lineares Programm. Dazu ersetzt man alle auftretenden Matrizen durch Diagonalmatrizen. Dadurch reduziert sich die Anforderung, dass $X$ positiv semidefinit sein soll zu $x_{i}\geq 0$, das Frobenius-Skalarprodukt geht zum Standardskalarprodukt über und damit werden die Gleichungsrestriktionen zu einem linearen Gleichungssystem.

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. $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.

Weblinks

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