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\succeq 0$

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\succeq 0$ 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

Literatur

• Florian Jarre und 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

• Englischsprachige Seite mit vielen weiterführenden Links