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.

approximation-hardness convex-optimization semidefinite-programming sum-of-squares primal-dual estudante de graduação
fonte

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 {t r (C^{T} X) : t r (A_{1}^{T} X) = b_{1}, \dots, t r (A_{m}^{T} X) = b_{m}, X ⪰ 0},

$\min\{ \mathrm{tr}(C^T X): \mathrm{tr}(A_1^T X) = b_1, \ldots, \mathrm{tr}(A_m^T X) = b_m, X \succeq 0\},$

X ≻ 0

$X\succ 0$

t r (A_{i}^{T} X) = b_{i}

$\mathrm{tr}(A_i^T X) = b_i$

{X : X_{1, 1} = 1, \dots, X_{n, n} = 1, X ⪰ 0}

$\{X: X_{1,1} = 1, \ldots, X_{n,n} = 1, X\succeq 0\}$

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}

$(P_{SD}) \,\, \sum_{i=1}^m x_i A_i \preceq B$

é mal comportado se houver uma função objetiva para a qual o SDP $c$

$\sup c^T x \,\, s.t. \,\, \sum_{i=1}^m x_i A_i \preceq B$

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 alguns $c.$

$(P_{SD})$ é 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. $(P_{SD})$

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

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

Distrito 9
fonte

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

Respostas: