A região viável deste SDP é poliédrica?

Temos um programa semidefinido (SDP) cuja região viável contém apenas um número finito de matrizes de classificação . Podemos concluir que a região viável desse SDP é poliédrica?$1$

Acreditamos que isso seja verdade, uma vez que a porção 'circular' do cone de matrizes semidefinidas se deve às matrizes extremas de classificação . Qualquer limite "curvo" da região viável deve ocorrer a partir de um número infinito de raios extremos.$1$

Como conseqüência, podemos afirmar que esse SDP pode ser resolvido exatamente no tempo polinomial, assim como programas lineares que também possuem uma região viável poliédrica?

Não, mesmo que exista um número finito de matrizes viáveis ​​de classificação 1, a região viável de um SDP não precisa ser poliédrica.

$S_n = \{X: X \succeq 0, X_{11} = \ldots = X_{nn} = 1\}$$n$$2^n$$S_n$$xx^T \in S_n$$x_i^2 = 1$$i$$x \in \{-1, 1\}^n$

$S_3$

$X \succeq 0$

$T$$S_3$$x, y, z$$U = T \cap \{(x, y, z): z = 0\}$$S_3$$U$$U = \{(x, y, 0): x^2 + y^2 \leq 1\}$

$U$$X$$u, v, w$$z = 0$$v \perp w$$(x, y)$$u$$v$$w$$v$$w$$u$$(x,y)$$1$

$T$

$U$