Resumo Técnico: Soma Disjuntiva de Quadrados

Declaração do Problema

O artigo aborda o problema fundamental de certificar a não negatividade de polinômios. Embora um polinômio $p$ seja não negativo se $p(x) \geq 0$ para todo $x \in \mathbb{R}^n$, determinar essa propriedade é geralmente NP-difícil. A abordagem padrão, o método da Soma de Quadrados (SOS), certifica a não negatividade expressando $p$ como uma única identidade algébrica $p(x) = \sum q_i^2(x)$. No entanto, nem todos os polinômios não negativos são SOS (um fato estabelecido por Hilbert), e provar a não negatividade para aqueles que não são tipicamente requer multiplicar $p$ por um polinômio SOS de alto grau (por exemplo, via solução de Artin para o 17º problema de Hilbert). Isso resulta em identidades algébricas com graus significativamente mais altos do que o polinômio original, levando a Programas Semidefinidos (SDPs) que crescem exponencialmente em tamanho e tornam-se computacionalmente intratáveis.

A questão central que motiva esta pesquisa é: A complexidade de uma prova baseada em SOS da não negatividade de polinômios pode ser reduzida construindo várias identidades algébricas em vez de uma única?

Metodologia

Os autores introduzem o conceito de Soma Disjuntiva de Quadrados (SOS Disjuntiva). Em vez de uma única identidade global, a não negatividade é certificada por uma coleção de identidades algébricas, cada uma válida em uma subregião específica do domínio. Essas subregiões formam uma partição (ou cobertura) do espaço, definida por uma disjunção algébrica.

Definições Principais

1. Disjunção Algébrica: Uma coleção de polinômios $\mathcal{D} = \{\{q_{k,j}\}\}$ tal que a união das regiões $\Omega_k = \{x \mid q_{k,j}(x) \geq 0, \forall j\}$ cobre $\mathbb{R}^n$.
2. Prova SOS Disjuntiva: Um polinômio $p$ é uma SOS disjuntiva em relação a $\mathcal{D}$ se, para cada região $\Omega_k$, existirem polinômios SOS $s_{k,j}$ tais que:
   $$p(x) = s_{k,0}(x) + \sum_{j=1}^{n_k} s_{k,j}(x)q_{k,j}(x) \quad \text{para todo } x \in \Omega_k.$$
   Crucialmente, o grau dos polinômios SOS $s_{k,j}$ pode ser mantido baixo (especificamente, limitado pelo grau de $p$), ao contrário das provas SOS globais onde o grau frequentemente precisa aumentar.

Estrutura Teórica

O artigo estabelece dois resultados teóricos principais, denominados Positivstellensätze Disjuntivos:

1. Positivstellensatz Disjuntivo Baseado em SDP (Teorema 1):
   Para qualquer forma definida positiva $p$ de grau $d$, existe uma família explícita de disjunções algébricas (construídas via calotas esféricas) tal que $p$ admite uma prova SOS disjuntiva onde o grau dos multiplicadores SOS é no máximo $d$. Isso permite uma hierarquia convergente de limites inferiores para minimização de polinômios sobre a esfera unitária usando SDPs de tamanho fixo (independente do nível da hierarquia).

2. Positivstellensatz Disjuntivo Livre de Otimização (Teorema 8):
   Um resultado mais forte mostrando que, para qualquer forma definida positiva, existe uma família de disjunções simpliciais (cones poliédricos) tal que $p$ pode ser certificado como não negativo simplesmente verificando que seus coeficientes são não negativos após uma mudança linear de coordenadas dentro de cada cone. Esta abordagem requer nenhum solucionador de otimização (apenas programação linear ou verificações diretas de coeficientes), mas pode exigir um número maior de regiões em comparação com a abordagem SDP.

Estrutura Algorítmica

Os autores propõem uma estrutura de Ramificação e Limitação Espacial (SBB) para buscar adaptativamente essas provas disjuntivas. Em vez de particionar uniformemente o espaço (como nas provas teóricas), o algoritmo:

• Mantém uma árvore de subregiões (cones simpliciais).
• Calcula limites inferiores via SDPs (ou verificações lineares) em cada subregião.
• Calcula limites superiores via descida de gradiente projetada.
• Ramifica bissectando a aresta mais longa da subregião com o menor limite inferior.
  Essa abordagem adaptativa visa encontrar certificados com menos subregiões do que construções uniformes.

Principais Contribuições e Resultados

1. Garantias Teóricas

• Grau Fixo: O artigo prova que provas SOS disjuntivas de baixo grau sempre existem. O grau dos polinômios SOS na prova não precisa crescer com o nível da hierarquia; pode ser fixado no grau do polinômio original.
• Convergência: Os autores constroem uma hierarquia de SDPs com restrições de tamanho fixo que converge para o mínimo global de um polinômio homogêneo sobre a esfera unitária. Eles estabelecem uma taxa de convergência de $O(1/m)$, onde $m$ está relacionado à resolução da partição espacial.
• Certificados Livres de Otimização: O segundo Positivstellensatz fornece um método para certificar a não negatividade sem resolver SDPs, confiando em vez disso em transformações lineares e verificações de não negatividade de coeficientes.

2. Aplicação à Otimização com Restrições

• Otimização Polinomial: Ao combinar a abordagem disjuntiva com uma técnica de redução de [2], os autores constroem uma hierarquia convergente de limites inferiores para problemas gerais de otimização polinomial (POPs) sobre conjuntos semialgébricos básicos compactos.
• Programação Copositiva: O método é especializado para certificar a copositividade de matrizes (verificando $x^T Q x \geq 0$ para $x \geq 0$). Os autores definem uma condição "Disjuntiva P+N" onde uma matriz é certificada como copositiva se, em cada subregião simplicial do ortante não negativo, puder ser decomposta em uma matriz semidefinida positiva e uma matriz não negativa. Isso produz uma hierarquia completa onde o tamanho da restrição SDP permanece fixo ($n \times n$), contrastando com hierarquias existentes onde o tamanho da restrição cresce polinomialmente com o nível.

3. Experimentos Numéricos

Os autores apresentam experimentos numéricos sobre:

• Polinômios Não-SOS: Os algoritmos certificaram com sucesso a não negatividade de polinômios clássicos não-SOS (por exemplo, Motzkin, Robinson, Choi-Lam, Delzell) usando um pequeno número de subregiões (frequentemente menos de 20) via estrutura SBB.
• Programas Copositivos: O algoritmo resolveu programas quadráticos não convexos e calculou o número de cliques de grafos (via teorema de Motzkin-Straus) em instâncias aleatórias.
• Desempenho: Os resultados indicam que a abordagem disjuntiva pode certificar a não negatividade e resolver problemas de otimização com significativamente menos subregiões do que a particionamento uniforme, e as restrições SDP permanecem gerenciáveis em tamanho.

Significado e Alegações

O artigo alega que a abordagem da soma disjuntiva de quadrados oferece uma alternativa viável às hierarquias SOS tradicionais, desacoplando a complexidade da prova (o grau dos polinômios SOS) do número de identidades algébricas utilizadas.

• Eficiência Computacional: Ao manter o grau dos polinômios SOS baixo e fixo, o tamanho dos SDPs subjacentes permanece constante ao longo da hierarquia, evitando a "maldição da dimensionalidade" associada ao aumento dos graus polinomiais nos métodos SOS padrão.
• Flexibilidade: A estrutura suporta tanto buscas baseadas em SDP (para limites mais apertados com menos regiões) quanto buscas livres de otimização (para certificados mais rápidos, embora potencialmente mais grosseiros).
• Completude: Os autores provam que esta abordagem é completa; para qualquer polinômio estritamente positivo (ou matriz estritamente copositiva), um certificado existe dentro de sua estrutura.

O artigo conclui observando que, embora as construções teóricas utilizem partições uniformes, o algoritmo SBB prático refina adaptativamente o espaço, sugerindo que disjunções específicas da instância poderiam reduzir ainda mais o número de regiões necessárias. O trabalho abre caminhos para combinar SOS disjuntiva com exploração de esparsidade e simetria, e para explorar o lado dual de momentos da estrutura.