Copositivity, discriminants and nonseparable signed supports

Resumo Técnico: Copositividade, Discriminantes e Suportes Assinados Não Separáveis

Enunciado do Problema
O artigo aborda o problema de determinar a copositividade de signomiais — funções definidas no ortante real positivo $\mathbb{R}^n_{>0}$ como combinações lineares de monomiais com expoentes reais. Especificamente, investiga-se a relação entre a fronteira do cone de signomiais copositivos, discriminantes e a estrutura combinatória do suporte assinado do signomial (o conjunto de expoentes pareados com os sinais de seus coeficientes). Embora a não negatividade global seja um tópico central na geometria algébrica real, decidir a pertinência ao cone de copositivos é um problema NP-difícil. Métodos existentes frequentemente dependem de certificados de não negatividade, tais como Somas de Quadrados (SOS), Somas de Circuitos Não Negativos (SONC) ou Somas de Exponenciais Aritmético-Geométricas (SAGE). Uma questão aberta fundamental é caracterizar os suportes assinados para os quais todo signomial copositivo admite uma decomposição SONC.

Metodologia
Os autores desenvolvem um critério para copositividade que se baseia na geometria do discriminante assinado e em métodos de continuação de homotopia.

1. Discriminantes Assinados e Caminhos: Os autores definem o discriminante assinado $(A^+, A^-)$, $\nabla_{>0}(A^+, A^-)$, como o conjunto de vetores de coeficientes para os quais o signomial (ou suas truncações para faces do fecho convexo do suporte) possui um zero singular positivo. Eles constroem um caminho específico no espaço de coeficientes, $c(t)$, que escala os coefs de termos negativos por um parâmetro $t$ enquanto preserva os sinais dos coeficientes.
2. Critério de Interseção: A ferramenta teórica central é a observação de que um signomial é copositivo se, e somente se, o caminho $c(t)$ não intersecta o discriminante assinado para qualquer $t < 1$. O conjunto de pontos de interseção $T$ é analisado para encontrar um valor mínimo $t^*$. A copositividade é equivalente a $t^* \geq 1$.
3. Suportes Assinados Não Separáveis: O artigo introduz o conceito combinatório de "suportes assinados não separáveis". Um par $(A^+, A^-)$ é não separável se $A^-$ estiver contido em uma célula $D$ do refinamento comum de todas as subdivisões poliedrais regulares de $A^+$. Esta condição geométrica generaliza casos conhecidos onde certificados SONC são garantidos.
4. Continuação de Homotopia: Para suportes não separáveis, os autores provam que o conjunto $T$ contém exatamente um elemento $t^*$. Isso permite o uso de continuação de homotopia de parâmetros para rastrear um único caminho de solução a partir de um ponto inicial conhecido (onde o signomial possui um zero singular em $x=1$) até o signomial alvo, evitando a necessidade de resolver múltiplos sistemas ou avaliar pontos críticos diretamente.

Principais Contribuições e Resultados

• Critério de Copositividade (Teorema A/Teorema 2.9): Os autores estabelecem uma condição necessária e suficiente para a copositividade. Para um signomial com suporte assinado $(A^+, A^-)$ onde $A^- \subseteq \text{conv}(A^+)$, a copositividade ocorre se, e somente se, o parâmetro mínimo $t^*$ no qual o caminho $c(t)$ intersecta o discriminante assinado (ou os discriminantes de suas truncações) satisfizer $t^* \geq 1$. Este critério evita os erros numéricos associados à avaliação do signomial em pontos críticos.
• Decomposição SONC para Suportes Não Separáveis (Teorema B/Teorema 3.16): O artigo prova que, para qualquer suporte assinado não separável onde $A^-$ reside no interior relativo de uma face de $\text{conv}(A^+)$, o cone de signomiais copositivos coincide com o cone SONC. Em outras palavras, todo signomial copositivo com tal suporte admite uma decomposição em uma soma de signomiais de circuitos não negativos. Isso generaliza resultados anteriores que exigiam condições geométricas específicas (ex: vértices simples).
• Unicidade e Não Degenerescência (Teoremo C/Teorema 3.17 & 4.5): Para suportes não separáveis, o conjunto de interseção $T$ consiste em exatamente um ponto $t^*$. Além disso, o sistema crítico correspondente possui um zero singular positivo único e não degenerado. Este resultado teórico garante que os métodos numéricos (continuação de homotopia) sejam robustos e eficientes para esta classe de problemas, pois não sofrem com a perda de soluções devido a conjuntos de zeros de dimensão positiva.
• Caracterização da Fronteira (Teorema 3.18): Os autores mostram que, para suportes assinados não separáveis, a fronteira algébrica do cone de polinômios copositivos está contida em (e iguala-se a, sob condições específicas, ao) o discriminante assinado.
• Implementação Computacional: O artigo apresenta o pacote Julia CopositivityDiscriminants.jl, que implementa estes métodos. Ele demonstra que, para suportes não separáveis, rastrear um único caminho de homotopia é significativamente mais eficiente (segundos vs. minutos) e numericamente estável comparado a rastrear todos os caminhos ou usar certificados SAGE, particularmente para signomiais muito próximos da fronteira do discriminante.

Significância e Alegações
O artigo afirma fornecer um framework unificado conectando discriminantes, copositividade e decomposições SONC. Sua principal significância reside em:

1. Generalização: Estende a classe conhecida de suportes assinados para os quais a copositividade implica decomponibilidade SONC para a classe mais ampla de suportes não separáveis, removendo suposições restritivas como a existência de vértices simples.
2. Eficiência Algorítmica: Ao provar que suportes não separáveis geram uma interseção única e não degenerada com o discriminante, os autores possibilitam uma estratégia computacional altamente eficiente (homotopia de caminho único) que evita a explosão combinatória de resolver múltiplos sistemas críticos.
3. Estabilidade Numérica: O método oferece um certificado de copositividade que é mais robusto do que métodos baseados em avaliação ou certificados SAGE ao lidar com signomiais próximos da fronteira do cone copositivo, conforme demonstrado por exemplos onde o SAGE falha para pequenas perturbações enquanto o método baseado em discriminante tem sucesso.

Os autores observam que, embora o método seja poderoso para suportes não separáveis, ele enfrenta limitações no caso geral onde os conjuntos de zeros de sistemas críticos podem ter dimensões positivas, potencialmente levando à perda de soluções em implementações numéricas. No entanto, eles mostram que, para coeficientes genéricos, tais patologias não ocorrem.