¿La región factible de este SDP es poliédrica?

8

Tenemos un programa semidefinido (SDP) cuya región factible contiene solo un número finito de matrices de rango . ¿Podemos concluir que la región factible de este SDP es poliédrica?1

Creemos que esto es cierto ya que la porción 'circular' del cono de matrices semidefinidas se debe a las matrices extremas de rango . Cualquier límite 'curvo' de la región factible debe ocurrir a partir de un número infinito de rayos extremos.1

Como consecuencia, ¿podemos afirmar que este SDP se puede resolver exactamente en tiempo polinomial al igual que los programas lineales que también tienen una región poliédrica factible?

Pawan Aurora
fuente

Respuestas:

15

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 TS n implica x 2 i =Sn={X:X0,X11==Xnn=1}n2nSnxxTSn para todo i , y por lo tanto x { - 1 , 1 } n .xi2=1ix{1,1}norte

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 2X0 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,z21X2+y2+z21+2Xyz
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 0}S3U es un disco.U={(X,y,0 0):X2+y21}

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 , yUXtu,v,wz=0 0vw(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 : Tingrese la descripción de la imagen aquí

Y aquí puedes ver que es un disco:U

ingrese la descripción de la imagen aquí

Sasho Nikolov
fuente
2
Debo decir que nunca antes traté de visualizar este espectraedro, y me parece interesante que simplemente parezca una versión ligeramente inflada del tetraedro formado por los puntos legales de rango 1. La sección que se muestra aquí como un círculo, es un cuadrado en el tetraedro.
Sasho Nikolov
Solo curiosidad por la segunda parte de mi pregunta. Digamos que existe un SDP con región factible poliédrica. ¿Qué opinas sobre su capacidad de resolución del tiempo polinómico exacto? Por cierto, gracias por la buena explicación.
Pawan Aurora
Pawan, a priori, no está claro para mí que si un SDP es poliédrico, tendría vértices racionales, y eso parece necesario para una solución exacta. Pero tengo problemas para imaginar un ejemplo. Quizás en todos los ejemplos poliédricos las restricciones de PSD no importan.
Sasho Nikolov
2
Xz=0 0X=yX[-1/ /2,1/ /2]
1
Por cierto, ¿no es el criterio de Sylvester para la definición positiva? Pensé que para pSd necesitabas verificar todos los menores principales para obtener un iff.
Suresh Venkat