Quando é que a diferença de dualidade da programação semidefinida (SDP) é zero?

10

Não pude encontrar na literatura uma caracterização precisa do desaparecimento da lacuna de dualidade do SDP. Ou quando é que a "forte dualidade" se aplica?

Por exemplo, quando se vai e volta entre o Lasserre e o SOS SDP, em princípio, há uma lacuna de dualidade. No entanto, de alguma forma, parece haver alguma razão "trivial" por que essa lacuna não existe.

A condição de Slater parece ser suficiente, mas não necessária, e se aplica a todos os programas convexos. Espero que, para os SDPs em particular, algo mais forte possa ser verdade. Eu ficaria igualmente feliz em ver qualquer exemplo explícito de usar a condição de Slater para provar o desaparecimento do hiato da dualidade.

estudante de graduação
fonte

Respostas:

10

Existe uma teoria mais complicada da dualidade para os SDPs que é exata: não existe uma 'condição extra' como a condição de Slater. Isto é devido a Ramana . (Para outra opinião sobre o SOS, consulte [KS12] .) Para ser sincero, nunca tentei entender esses papéis e ficaria feliz se alguém os enganasse por mim.

Uma conseqüência notável deste trabalho é que o problema de testar se um determinado SDP é viável está no NP se e somente se estiver no coNP. (No entanto, acho que os especialistas esperam que o problema não ocorra. O melhor limite superior conhecido é o PSPACE.)

Ryan O'Donnell
fonte
Muito obrigado pela resposta muito útil! Deixe-me procurar! (Que coincidência, nas últimas semanas, eu também tenho tentado trabalhar com o seu trabalho com Daniel Kane nos limites inferiores do circuito de rede profunda! ativações realistas como ReLU.)
gradstudent
9

min{tr(CTX):tr(A1TX)=b1,,tr(AmTX)=bm,X0},
X0tr(AiTX)=bi{X:X1,1=1,,Xn,n=1,X0}

No que diz respeito à hierarquia de Lasserre / Soma dos Quadrados, Lasserre mostrou que se o conjunto viável determinado pelas restrições polinomiais tem um ponto interior, então não há diferença de dualidade. Você pode encontrar uma condição mais fraca neste documento .

Sasho Nikolov
fonte
Muito obrigado pelas referências! Então, a condição de Slater transformado também é uma condição necessária para o SDP? Ou existem outras condições necessárias? (Em breve, examinarei os documentos a que você se referiu, mas eu queria saber se você poderia dizer algo sobre o que você quis dizer com "condição mais fraca". Você quer dizer que a condição no segundo artigo ainda é uma condição suficiente e não necessária condição, mas é mais simples do que a condição suficiente no primeiro papel)?
gradstudent
Essa é a condição padrão do Slater, que acabei de especializar para SDPs, o que simplifica as coisas porque todas as restrições são afins, exceto a restrição do PSD. Esta condição não é necessária. Também não acho que nenhuma das condições SoS seja necessária, mas a "mais fraca" não exige a existência de um ponto interior, portanto, pode ser mais fácil verificar.
Sasho Nikolov
Obrigado! Então, uma condição necessária não é conhecida?
gradstudent
1

Existe uma boa caracterização (eu acho ...) de quando uma forte dualidade se mantém ou falha em {\ em all} funções objetivas.

Dizemos que o sistema semidefinido {\ em}

(PSD)i=1mxiAiB

é mal comportado se houver uma função objetiva para a qual o SDPc

supcTxs.t.i=1mxiAiB

possui um valor ótimo finito, mas o SDP duplo não possui uma solução com o mesmo valor: ou seja, uma dualidade forte falha para algunsc.

(PSD) é bem comportado se não for mal comportado. Ou seja, para toda função objetiva a dualidade forte é válida. (Ou seja, para cada para o qual o SDP primordial tem um valor ótimo finito, o dual tem uma solução com o mesmo valor).c

Obviamente, se a condição de Slater se mantiver, então será bem comportada, mas o inverso não será verdadeiro.(PSD)

https://arxiv.org/pdf/1709.02423.pdf

O artigo será publicado em breve na SIAM Review. Espero que as pessoas gostem :)

Distrito 9
fonte