No, incluso si hay un número finito de matrices de rango 1 factibles, la región factible de un SDP no tiene que ser poliédrica.
Un espectroedro que se ve todo el tiempo en las aplicaciones es , es decir, el conjunto de matrices de Gram de n vectores unitarios. Esta es, por ejemplo, la región factible para la relajación Goemans-Williamson SDP para MaxCut. No puede haber más de 2 n matrices de rango 1 en S n , porque x x T ∈ S n implica x 2 i =Sn={X:X⪰0,X11=…=Xnn=1}n2nSnxxT∈Sn para todo i , y por lo tanto x ∈ { - 1 , 1 } n .x2i=1ix∈{−1,1}n
Ahora echemos un vistazo a . EscribirS3
X= ⎛⎝⎜1XyX1zyz1⎞⎠⎟
Según el criterio de Sylvester , si y solo si todos los menores principales no son negativos. Esto da las siguientes desigualdades:
x 2 , y 2 , z 2X⪰ 0
Las tres primeras desigualdades provienen de la escritura de los menores de edad de 2 por 2, y el último viene de escribir el determinante deX.
X2, y2, z2X2+ y2+ z2≤ 1≤ 1 + 2 x yz
X
Ahora es fácil ver que este conjunto no es poliédrico. Por ejemplo, deje que el conjunto sea la proyección de S 3 sobre las variables libres x , y , z , y considere U = T ∩ { ( x , y , z ) : z = 0 } . Los conjuntos poliédricos siguen siendo poliédricos después de la proyección ortogonal y la intersección con medios espacios, por lo que si S 3 es poliédrico, entonces U también lo es. Pero U = { ( x , yTS3x , y, zU= T∩ { ( x , y, z) : z= 0 }S3U es un disco.U= { ( x , y, 0 ) : x2+ y2≤ 1 }
De hecho, también hay un argumento geométrico directo de que es un disco. Si X es la matriz de Gram de los vectores u , v , w , entonces establecer z = 0 significa v ⊥ w , y ( x , y ) son las coordenadas de la proyección de u en el plano atravesado por v y w , expresado en La base ortonormal dada por v y w . Como u puede ser cualquier vector unitario, ( x , yUXu , v , wz= 0v ⊥ w( x , y)tuvwvwtu puede ser cualquier vector de longitud como máximo 1 .( x , y)1
A modo de ilustración, aquí está el conjunto :
T
Y aquí puedes ver que es un disco:U