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

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

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

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

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

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

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

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

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.