##  [Semidefinite Programmierung](/de/node/59740) 

 Definition

Eine Klasse konvexer Optimierungsprobleme, bei denen eine lineare Zielfunktion unter affinen (linearen) Nebenbedingungen und einer symmetrischen Matrixvariablen, die positiv semidefinit sein muss, optimiert wird.

 

 

 

 

 

 





## Prinzip

Prinzip

Ersetze nichtkonvexe Matrixbeschränkungen durch den konvexen Kegel der positiv semidefiniten Matrizen; forme lineare Matrixungleichungen und lineare Zielfunktionen, um ein Problem zu erhalten, das mit Innenpunkt- oder First-Order-Konvexmethoden lösbar ist.

 

 

 

 

 





## Demonstration

Demonstration

Minimiere trace(CX) unter den Nebenbedingungen trace(A_i X) = b_i für i = 1..m und X >= 0 (X positiv semidefinit); diese Formulierung erfasst Relaxationen kombinatorischer Probleme sowie Entwurfsaufgaben in Regelung und Signalverarbeitung.

 

 

 

 

## Fehlanwendung

Fehlanwendung

SDP-Relaxationen fälschlich als exakte Lösungen zu betrachten, ohne Rangbedingungen oder Integritätsanforderungen zu prüfen, kann zu zu optimistischen Ergebnissen führen; dichte SDP-Solver auf sehr große, spärliche Probleme anzuwenden, ohne Struktur auszunutzen, ist praktisch unbrauchbar.

 

 

 

 

 





## Konsequenz

Konsequenz

Bei geeigneter Anwendung liefert SDP enge konvexe Relaxationen für viele schwierige Probleme, ermöglicht im Innenpunkt-Sinn polynomiell lösbare Probleme und bietet über duale Lösungen Zertifikate für Optimalität oder Unzulässigkeit.

 

 

 

 

## Umkehrung

Umkehrung

Die Umkehr ist die Beschränkung auf lineare Programmierung durch Erzwingen diagonaler Matrixvariablen oder Weglassen der PSD-Bedingungen, was die Berechnung vereinfacht, jedoch die Modellierungsfähigkeit für Korrelationen und quadratische Formen verliert.

 

 

 

 

 





## Abgrenzung

Abgrenzung

Gilt für Probleme, die sich mit linearen Matrixungleichungen und symmetrischen PSD-Matrixvariablen ausdrücken lassen; schließt inhärent nichtkonvexe Zielfunktionen oder Nebenbedingungen sowie Fälle aus, in denen ganzzahlige Beschränkungen ohne Relaxation zwingend sind.

 

 

 

 

 





## Semantische Spannung

Semantische Spannung

Spannung zwischen Genauigkeit der Lösung (Enge der SDP-Relaxation) und rechnerischer Machbarkeit (Größe und Ausnutzung von Sparsity) sowie zwischen dichten Innenpunktlösern (hohe Genauigkeit) und First-Order-Methoden (Skalierbarkeit, aber schwächere Abbruchgarantien).

 

 

 

 

 





## Synthese

Synthese

Semidefinite Programmierung stellt Probleme mit Matrixvariablen und PSD-Beschränkungen als konvexe Programme dar: lineare Ziele plus lineare Matrixungleichungen definieren eine handhabbare Kegeloptimierung, die Modellstärke und algorithmische Komplexität austariert.