Ist die realisierbare Region dieser SDP polyedrisch?

8

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?

Pawan Aurora
quelle

Antworten:

15

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 TS n x 2 i = impliziertS.n={X.::X.0,X.11==X.nn=1}}n2nS.nxxT.S.n für alle i und damit x { - 1 , 1 } n .xich2=1ichx{- -1,1}}n

Schauen wir uns nun . SchreibenS.3

X.=(1xyx1zyz1)

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

x2,y2,z21x2+y2+z21+2xyz
X

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 , yTS3x,y,zU.=T.{(x,y,z)::z=0}}S.3U. ist eine Scheibe.U.={(x,y,0)::x2+y21}}

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 , yU.X.u,v,wz=0vw(x,y)uvwvwu kann höchstens ein beliebiger Längenvektor sein 1 .(x,y)1

Zur Veranschaulichung ist hier die Menge : T.Geben Sie hier die Bildbeschreibung ein

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

Geben Sie hier die Bildbeschreibung ein

Sasho Nikolov
quelle
2
Ich sollte sagen, ich habe noch nie versucht, dieses Spektraeder zu visualisieren, und ich finde es interessant, dass es einfach wie eine leicht aufgeblasene Version des Tetraeders aussieht, das durch die legalen Rang-1-Punkte gebildet wird. Der Abschnitt, der hier als Kreis dargestellt ist, ist ein Quadrat im Tetraeder.
Sasho Nikolov
Ich bin nur neugierig auf den zweiten Teil meiner Frage. Angenommen, es gibt ein SDP mit einer polyedrischen realisierbaren Region. Was halten Sie von der genauen Lösbarkeit der Polynomzeit? Übrigens danke für die nette Erklärung.
Pawan Aurora
Pawan, apriori, es ist mir nicht klar, dass ein polyedrisches SDP rationale Eckpunkte haben würde, und das scheint für eine genaue Lösbarkeit notwendig zu sein. Aber ich habe Probleme, mir ein Beispiel vorzustellen. Vielleicht spielen in allen polyedrischen Beispielen die PSD-Einschränkungen keine Rolle.
Sasho Nikolov
2
X.z=0x=yx[- -1/.2,1/.2]]
1
Übrigens ist Sylvesters Kriterium für eine positive Bestimmtheit nicht? Ich dachte, dass Sie für pSd alle Hauptminderjährigen überprüfen müssen, um ein iff zu erhalten.
Suresh Venkat