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, der optimalen Versuchsplanung und 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} (A^{T}B)=\operatorname {tr} (AB^{T})$.

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, die sogenannte Loewner-Halbordnung.

Normalform

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}$ ist ein lineares semidefinites Programm oder einfach semidefinites Programm (kurz SDP) in Normalform. 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. Manchmal werden auch die $m$ Gleichungsnebenbedingungen zusammengefasst durch eine Lineare Funktion $L(X):S^{n}\mapsto \mathbb {R} ^{m}$, die durch

$L(X):={\begin{pmatrix}\langle {A_{1}},{X}\rangle _{F}\\\vdots \\\langle {A_{m}},{X}\rangle _{F}\end{pmatrix}}$

definiert ist. Dann lauten die Ungleichungsnebenbedingungen $L(X)=b$ mit $b\in \mathbb {R} ^{m}$.

Ungleichungsform

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. Gelegentlich wird die Ungleichungsform auch geschrieben als

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

Hierbei entspricht $S$ der Einführung einer Schlupfvariable. Diese Form wird gerne gewählt, um Analogien zu den linearen Programmen klarzumachen. Auch hier wird gelegentlich eine lineare Funktion $L^{*}(x):\mathbb {R} ^{m}\mapsto S^{n}$ definiert durch

$L^{*}(x)=x_{1}A_{1}+\dots +x_{m}A_{m}$,

um die Notation zu vereinfachen und spätere Dualitätsaussagen klarer zu machen.

Ohne verallgemeinerte Ungleichungen

Formuliert man SDP ohne verallgemeinerte Ungleichungen, so werden die Bedingungen $X\succcurlyeq _{S_{+}^{n}}0$ (Normalform) und $S\succcurlyeq _{S_{+}^{n}}0$ (Ungleichungsform mit Schlupfvariable) meist ausgeschrieben als „$X$ (bzw- $S$) ist positiv semidefinit“.

Nichtlineare semidefinite Programme

Gelegentlich werden auch nichtlineare semidefinite Programme betrachtet, diese haben dann entweder keine lineare Zielfunktion mehr oder nichtlineare Restriktionen.

Klassifikation und Spezialfälle

Als konvexe Optimierungsprobleme

Semidefinite Programme sind immer konvexe Optimierungsprobleme. Dies folgt daraus, dass alle Gleichungsrestriktionen immer affin-linear sind und alle Ungleichungsrestriktionen (unter Verwendung von verallgemeinerten Ungleichungen) immer affin-linear sind und damit auch immer K-konvexe Funktionen sind. Damit ist die Restriktionsmenge konvex. Da außerdem die Zielfunktion immer linear ist, handelt es sich immer um ein (abstraktes oder verallgemeinertes) konvexes Problem, unabhängig ob es als Minimierungsproblem oder als Maximierungsproblem formuliert ist.

Als konisches Programm

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. Der lineare Unterraum des $S^{n}$ wird in der Normalform durch den Kern der Abbildung $L:S^{n}\mapsto \mathbb {R} ^{m}$, also durch die Lösungsmenge der Gleichung $L(X)=0$, beschreiben. In der Ungleichungsform mit Schlupfvariable wird der Unterraum durch das Bild der Abbildung $L^{*}:\mathbb {R} ^{m}\mapsto S^{n}$ beschrieben.

Spezialfall lineare Programme

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.

Dualität

Lagrange-Dualität

Ist ein SDP in Normalform gegeben durch

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

so lässt sich das duale Problem bezüglich der Lagrange-Dualität wie folgt formulieren. Man formuliert die Gleichungsnebenbedingungen um zu $-\langle {A_{i}},{X}\rangle _{F}+b_{i}=0$. Damit erhält man als Lagrange-Funktion

$L(X,\Lambda ,\mu )=\langle {C},{X}\rangle _{F}+\langle {-X},{\Lambda }\rangle _{F}+\sum _{i=1}^{m}\mu _{i}(-\langle {A_{i}},{X}\rangle _{F}+b_{i})$.

und unter Ausnutzung der Selbstdualität des semidefiniten Kegels das duale Problem

${\begin{aligned}{\text{Maximiere }}&\mu ^{T}b\\{\text{unter den Nebenbedingungen }}&\mu _{1}A_{1}+\dots +\mu _{m}A_{m}-\Lambda =-C\\&\Lambda \succcurlyeq _{S_{+}^{n}}0\end{aligned}}$.

$\Lambda$ fungiert hier als Schlupfvariable. Dies ist ein SDP in Ungleichungsform. Für das genaue Vorgehen siehe Lagrange-Dualität konischer Programme.

Analog zu den konischen Programmen erhält man auch als duales Problem eines SDPs in Ungleichungsform

${\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}}$

das SDP in Normalform

${\begin{aligned}{\text{Maximiere }}&s(\Lambda )=-\langle {\Lambda },{B}\rangle _{F}&\\{\text{unter den Nebenbedingungen }}&\Lambda \succcurlyeq _{S_{+}^{n}}&\\&\langle {\Lambda },{A_{i}}\rangle _{F}=-c_{i}&i=1,\dots ,m\end{aligned}}$,

Somit sind die SDPs abgeschlossen bezüglich der Lagrange-Dualität und das duale Problem des dualen Problems ist stets wieder das primale Problem. Außerdem gilt stets die schwache Dualität, also dass der Zielfunktionswert des dualen Problems stets kleiner ist als der Zielfunktionswert des primalen Problems. Ist außerdem die Slater-Bedingung erfüllt (siehe unten), so gilt die starke Dualität, die Optimalwerte des primalen und des dualen Problems stimmen also überein.

Dualität konischer Programme

Fasst man SDPs als abstrakte konische Programme auf, so lässt sich der lineare Unterraum ${\mathcal {L}}$ durch die oben beschriebene lineare Funktion $L:S^{n}\mapsto \mathbb {R} ^{m}$ beschreiben. Er ist dann genau die Lösungsmenge der Gleichung $L(X)=0$. Somit lässt sich das primale konische Problem als SDP in Normalform schreiben.

${\begin{aligned}{\text{Minimiere }}&s(X)=\langle {C},{X}\rangle _{F}\\{\text{unter den Nebenbedingungen }}&X\succcurlyeq _{S_{+}^{n}}0\\&L(X)-b=0\end{aligned}}$

Hierbei sei $L(B)=b$. Der für das duale Problem nötige Orthogonalraum wird dann durch den zu $L$ adjungierten Operator $L^{*}:\mathbb {R} ^{m}\mapsto S^{n}$, der durch $L^{*}(x)=x_{1}A_{1}+\dots +x_{m}A_{m}$ definiert ist, beschrieben. Somit lautet das konische duale Problem:

${\begin{aligned}{\text{Minimiere }}&s(Y)=\langle {B},{Y}\rangle _{F}\\{\text{unter den Nebenbedingungen }}&Y\succcurlyeq _{S_{+}^{n}}0\\&Y=L^{*}(y)+C,\,y\in \mathbb {R} ^{m}\end{aligned}}$.

Das duale Problem ist dann also ein SDP in Ungleichungsform mit Schlupfvariable. Es gilt dann stets für alle zulässigen $X,Y$

$\langle {C},{X}\rangle _{F}+\langle {B},{Y}\rangle _{F}\geq \langle {B},{C}\rangle _{F}$

Ist die Slater-Bedingung erfüllt (siehe unten) und das primale Problem hat einen endlichen Optimalwert $p^{*}$, so hat das duale Problem eine Optimallösung $Y^{*}$, und es gilt

$p^{*}+\langle {B},{Y^{*}}\rangle _{F}=\langle {B},{C}\rangle _{F}$.

Slater-Bedingung

Die Slater-Bedingung ist eine Voraussetzung an das primale Problem, die garantiert, dass starke Dualität gilt. Sie fordert, dass das Problem einen Punkt besitzt, der die Gleichungsnebenbedingungen erfüllt, und alle Ungleichungsnebenbedingungen strikt erfüllt, dass also $f(x)\prec _{K}0$ bzw. $f(x)\succ _{K}0$ für mindestens einen Punkt $x$ in allen Ungleichungsnebenbedingungen des Problems gleichzeitig gilt. Da aber $X\succ _{S_{+}^{n}}0$ genau dann gilt, wenn $X\in \operatorname {Int} (S_{+}^{n})$ ist, was wiederum äquivalent dazu ist, dass $X$ eine positiv definite Matrix ist, ist die Slater-Bedingung für SDPs bereits erfüllt, wenn es eine positiv definite Matrix gibt, welche die Gleichungsnebenbedingungen erfüllt.

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