Semidefinite Optimierung

Semidefinite Optimierung

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.

Inhaltsverzeichnis

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


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • 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… …   Deutsch Wikipedia

  • Konvexe Optimierung — Die Konvexe Optimierung ist ein Teilgebiet der mathematischen Optimierung. Es ist eine bestimmte Größe zu minimieren, die sogenannte Zielfunktion, welche von einem Parameter, welcher mit x bezeichnet wird, abhängt. Außerdem sind bestimmte… …   Deutsch Wikipedia

  • Kkt — Die Konvexe Optimierung ist ein Teilgebiet der mathematischen Optimierung. Es ist eine bestimmte Größe zu minimieren, die sogenannte Zielfunktion, welche von einem Parameter, welcher mit x bezeichnet wird, abhängt. Außerdem sind bestimmte… …   Deutsch Wikipedia

  • Kuhn-Tucker-Bedingungen — Die Konvexe Optimierung ist ein Teilgebiet der mathematischen Optimierung. Es ist eine bestimmte Größe zu minimieren, die sogenannte Zielfunktion, welche von einem Parameter, welcher mit x bezeichnet wird, abhängt. Außerdem sind bestimmte… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”