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

8

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?

Pawan Aurora
fonte

Respostas:

15

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.

Sn={X:X0,X11==Xnn=1}n2nSnxxTSnxi2=1ix{1,1}n

S3

X=(1xyx1zyz1)

X0

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

TS3x,y,zU=T{(x,y,z):z=0}S3UU={(x,y,0):x2+y21}

UXu,v,wz=0vw(x,y)uvwvwu(x,y)1

Tinsira a descrição da imagem aqui

U

insira a descrição da imagem aqui

Sasho Nikolov
fonte
2
Devo dizer que nunca tentei visualizar esse espectroedro antes e acho interessante que ele simplesmente se pareça com uma versão levemente inflada do tetraedro formada pelos pontos legais de classificação 1. A seção que é mostrada aqui como um círculo é um quadrado no tetraedro.
Sasho Nikolov
Apenas curioso sobre a segunda parte da minha pergunta. Digamos que exista um SDP com região viável poliédrica. O que você acha da exata solvabilidade do tempo polinomial? Btw obrigado pela boa explicação.
Pawan Aurora
Pawan, a priori, não está claro para mim que, se um SDP for poliédrico, ele terá vértices racionais, e isso parece necessário para a exata resolubilidade. Mas estou tendo problemas para imaginar um exemplo. Talvez em todos os exemplos poliédricos as restrições do PSD não importem.
Sasho Nikolov
2
Xz=0x=yx[1/2,1/2]
1
Btw não é o critério de Sylvester para definição positiva? Eu pensei que, para pSd, você precisava verificar todos os principais menores de idade para obter um iff.
precisa