Semidefinite Programmierung

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

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[Bearbeiten]

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. \mathrm{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[Bearbeiten]

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[Bearbeiten]

  • 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[Bearbeiten]

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

Weblinks[Bearbeiten]