Ist die realisierbare Region dieser SDP polyedrisch?

Wir haben ein semidefinites Programm (SDP), dessen realisierbare Region nur eine endliche Anzahl von Rang- Matrizen enthält. Können wir daraus schließen, dass die realisierbare Region dieses SDP polyedrisch ist?$1$

Wir glauben, dass dies wahr ist, da der 'kreisförmige' Teil des Kegels der semidefiniten Matrizen auf die extremen Rang- Matrizen zurückzuführen ist. Jede "gekrümmte" Grenze des realisierbaren Bereichs muss aus einer unendlichen Anzahl extremer Strahlen bestehen.$1$

Können wir folglich behaupten, dass dieses SDP genau in linearer Zeit in Polynomzeit gelöst werden kann, genau wie lineare Programme, die ebenfalls einen polyedrischen realisierbaren Bereich haben?

Nein, selbst wenn es eine endliche Anzahl von realisierbaren Rang-1-Matrizen gibt, muss der realisierbare Bereich eines SDP nicht polyedrisch sein.

Ein Spektraeder, das Sie in Anwendungen ständig sehen, ist , dh die Menge der Gram-Matrizen von n Einheitsvektoren. Dies ist beispielsweise die realisierbare Region für die Goemans-Williamson SDP-Relaxation für MaxCut. Es kann nicht mehr als 2 n Rang-1-Matrizen in S n geben , da x x T ∈ S n x 2 i = impliziert$S_n = \{X: X \succeq 0, X_{11} = \ldots = X_{nn} = 1\}$$n$$2^n$$S_n$$xx^T \in S_n$ für alle i und damit x ∈ { - 1 , 1 } n .$x_i^2 = 1$$i$$x \in \{-1, 1\}^n$

Schauen wir uns nun . Schreiben$S_3$

Nach Sylvesters Kriterium ist genau dann, wenn alle Hauptminderjährigen nicht negativ sind. Dies ergibt die folgenden Ungleichungen: x 2 , y 2 , z $X \succeq 0$ Die ersten drei Ungleichungen kommen von den Minderjährigen 2-by-2schreiben, und der letzte kommt von der Determinante des SchreibensX.

Es ist jetzt leicht zu erkennen, dass dieses Set nicht polyedrisch ist. Zum Beispiel sei die Menge die Projektion von S 3 auf die freien Variablen x , y , z und betrachte U = T ∩ { ( x , y , z ) : z = 0 } . Polyedrische Mengen bleiben nach orthogonaler Projektion und Schnittpunkt mit Halbräumen polyedrisch. Wenn also S 3 polyedrisch ist, ist auch U polyedrisch . Aber U = { ( x , $T$$S_3$$x, y, z$$U = T \cap \{(x, y, z): z = 0\}$$S_3$$U$ ist eine Scheibe.$U = \{(x, y, 0): x^2 + y^2 \leq 1\}$

Tatsächlich gibt es auch ein direktes geometrisches Argument, dass eine Scheibe ist. Wenn X die Gram - Matrix der Vektoren u , v , w , dann Einstellen z = 0 Mittel v ⊥ w , und ( x , y ) sind die Koordinaten der Projektion der U auf die Ebene , die durch aufgespannten v und w , ausgedrückt in die orthonormale Basis gegeben durch v und w . Da u ein beliebiger Einheitsvektor sein kann, ( x , $U$$X$$u, v, w$$z = 0$$v \perp w$$(x, y)$$u$$v$$w$$v$$w$$u$ kann höchstens ein beliebiger Längenvektor sein 1 .$(x,y)$$1$

Zur Veranschaulichung ist hier die Menge : $T$

Und hier können Sie sehen, dass eine Scheibe ist:$U$