Precisão numérica no método da soma dos quadrados?

13

Eu tenho lido um pouco sobre o método da soma dos quadrados (SOS) da pesquisa de Barak & Steurer e das notas de aula de Barak . Nos dois casos, eles varrem questões de precisão numérica para baixo do tapete.

Do meu entendimento (reconhecidamente limitado) do método, o seguinte deve ser verdadeiro:

Dado qualquer sistema de igualdades polinomiais sobre variáveis ​​de valor real x R n , em que todos os parâmetros são O ( 1 ) ( n , | E | e grau de cada restrição), o grau- " 2 n " ( = O ( 1 ) ) O método SOS encontra uma atribuição satisfatória das variáveis ​​ou prova que não existe no tempo O ( 1 ) . ExRnO(1)n|E|2n=O(1)O(1)

Minha primeira pergunta é se a afirmação acima é verdadeira (existe um argumento ingênuo que não usa o SOS para resolver isso?). A segunda pergunta é onde a precisão numérica se encaixa. Se eu quiser obter uma atribuição que satisfaça todas as restrições com precisão aditiva , como o tempo de execução depende de 1 / ε ? Em particular, é polinomial?ε1/ε

A motivação para isso é, por exemplo, aplicar uma abordagem de dividir e conquistar em um sistema grande até que o caso base seja um sistema de tamanho .O(1)

EDIT: De Barak-Steurer, parece que o " algoritmo da soma dos quadrados em graus " na p.9 (e os parágrafos anteriores) definem problemas para soluções em vez de R e, de fato, a definição de um pseudo -Distribuição na seção 2.2 é mais de R . Agora estou vendo no Lema 2.2, no entanto, que não é garantida uma solução / refutação no grau 2 n sem variáveis ​​binárias.lRR2n

Para refinar minha pergunta um pouco. Se suas variáveis ​​não são binárias, a preocupação é que a sequência de saídas não seja finita (talvez nem mesmo monotônica aumente?). Portanto, a questão é: φ ( l ) ainda está aumentando? E se sim, até que ponto você precisa ir para obter a precisão aditiva ε ?φ(l)φ(l)ε

Embora isso provavelmente não muda nada, acontece que eu sei que meu sistema é satisfiable (não há refutação de qualquer grau), então eu realmente estou apenas preocupado com o quão grande precisa ser. Finalmente, estou interessado em uma solução teórica, não em um solucionador numérico.l

Jeremy Kun
fonte

Respostas:

1

Aqui está o comentário de Boaz Barak sobre o assunto:

Nós varremos a precisão numérica para baixo do tapete - a literatura SOS mais "tradicional" de Parrilo, Lasserre etc. lida com essas questões (por exemplo, consulte as pesquisas de Monique Laurent e as referências nela). Sabe-se que a hierarquia é monótona (não é difícil ver que um grau de distribuição psuedo é em particular um grau l - 1 ), e que convergirá em grau finito para qualquer conjunto fixo de equações (isto é Positivstellensatz). O grau exato pode variar. Geralmente, se todos os coeficientes dos polinômios estiverem delimitados e você estiver tentando distinguir entre o caso em que existe uma solução e o caso em qualquer atribuição em que uma das equações está desativada por ϵ , pode-se discretizar isso para umll1ϵ -net para δ relacionado ao número de variáveis, grau de equações e ϵ , e então (supondo que a rede seja suficientemente "agradável" e "parecida com cubo"), o grau necessário deve ser aproximadamente o tamanho da rede.δδϵ

Kaveh
fonte
Postado como uma resposta para evitar que o bot da comunidade troque a pergunta novamente no futuro.
Kaveh
1

Acho que minha resposta provavelmente é insuficiente, mas permanece por uma questão de integridade (embora veja os comentários de Boaz abaixo para provavelmente uma resposta melhor)

Quando nos limitamos a variáveis ​​booleanas, a afirmação pode ser vista quando para todos i [ n ] com a observação de que as pseudo-distribuições de grau 2 n são distribuições reais, ou seja, suponha que você tenha uma pseudo-distribuição μ ( x ) sobre as soluções x das suas igualdades polinomiais E satisfazendo:(xi21)Ei[n]2nμ(x)xE

ex { - 1 , 1 } n μ ( x ) p 2 ( x ) 0 para todos os polinômios p com grau no máximo nx{1,1}nμ(x)x{1,1}nμ(x)p2(x)0pn

Mas os polinômios de grau incluem o polinômio indicador (por exemplo, x 1 = 1 , x 2 = - 1 , x 3 = 1 possui 2 - 3 ( 1 + x 1 ) ( 1 - x 2 ) ( 1 + x 3 ) que é zero em qualquer outro lugar e 1 nessa atribuição). Então μ ( x ) 0 para todos x {nx1=1,x2=1,x3=123(1+x1)(1x2)(1+x3)μ(x)0 , portanto, concluir μ é uma distribuição efectiva sobre as soluções de E . Grau l pseudo-distribuições podem ser encontrados através da utilização de programação semidefinido para encontrar um grau associado operador pseudo-expectativa em n ó ( ) tempo, de modo que podemos encontrar a distribuição real μ no tempo N O ( n ) através da utilização desse pseudo expectativa (agora uma expectativa real) de encontrar todos os momentos de μ .x{1,1}nμEnO()μnO(n)μ

Então se , você pode encontrar uma distribuição de soluções para E no tempo de O ( 1 ) . Obviamente, a busca por força bruta garante o mesmo.|E|=O(1)EO(1)

No entanto, se as soluções não forem necessariamente booleanas, as pseudo-expectativas de grau não serão suficientes para encontrar uma distribuição entre as soluções. Como pode ser visto acima, a prova de que as pseudo-distribuições do grau 2 n são distribuições reais depende do fato de que os polinômios do grau n são suficientes para 'selecionar' as atribuições individuais, o que não é verdade de maneira mais geral. Outra maneira de ver é que polinômios de variável booleana são considerados2n2nn , então o grau de todo monômio é no máximo n .mod(xi2)n

Por exemplo, pode-se considerar a substituição de cada variável binária com uma variável 4-ário, digamos, incluindo . Então você teria que ter uma pseudo-expectativa de grau 4 n para garantir a recuperação de uma distribuição sobre soluções.(xi21)(xi24)E4n

Agora, para garantias teóricas, parece que aproximar a raiz de um sistema de polinomal também é conhecido como o 17º problema de Smale e, aparentemente, existe um algoritmo de tempo polinomial aleatório (Las Vegas) que resolve isso - veja http://arxiv.org /pdf/1211.1528v1.pdf . Observe que isso parece estar no modelo Blum-Shub-Smale, portanto, as operações reais são as primitivas. Não tenho certeza se isso dá a garantia de que você precisa.

Joe Bebel
fonte
Acho que posso não ter esclarecido isso: minhas variáveis estão em R , pois, caso contrário, eu poderia fazer uma pesquisa trivial de O ( 2 n ) = O ( 1 ) sobre o hipercubo booleano. Atualizei a pergunta para refletir isso. O SDP / SOS também se aplica a problemas de otimização de entrada real, certo? xiRO(2n)=O(1)
Jeremy Kun
Opa, meu erro! Sim, isso se aplica a configurações mais gerais, embora muitas vezes apenas assumamos que estamos no hipercubo. Atualizei minha resposta, embora minha resposta seja menos clara do que eu esperava.
Joe Bebel
10
Nós varremos a precisão numérica para debaixo do tapete - a literatura SOS mais "tradicional" de Parrilo, Lasserre etc. lida com essas questões (por exemplo, consulte as pesquisas de Monique Laurent e as referências nela). Sabe-se que a hierarquia é monótona (não é difícil ver que um grau distribuição psuedo é particularmente um grau - 1 um) e que convergirá em grau finito para qualquer conjunto fixo de equações (isto é Positivstellensatz). 1
Boaz Barak
9
..O grau exato pode variar. Geralmente, se todos os coeficientes dos polinômios estiverem delimitados e você estiver tentando distinguir entre o caso em que existe uma solução e o caso em qualquer atribuição, uma das equações estiver desativada por , seria possível discretizá-lo para δ - net para δ relacionado ao número de variáveis, grau de equações e ϵ , e então (supondo que a rede seja suficientemente "agradável" e "parecida com cubo"), o grau necessário deve ser aproximadamente o tamanho da rede. ϵδδϵ
Boaz Barak
4
@BoazBarak talvez isso possa ser uma resposta?
Suresh Venkat