Perfect Copositive Matrices

Resumo Técnico: Matrizes Copositivas Perfeitas

Enunciado do Problema
O artigo aborda o estudo sistemático de "matrizes copositivas perfeitas", uma generalização das clássicas matrizes positivas definidas perfeitas no contexto da otimização copositiva. A principal motivação é a solução algorítmica para o problema de encontrar certificados racionais para matrizes completamente positivas (CP). Uma matriz $Q$ é completamente positiva se admite uma decomposição $Q = \sum \alpha_i x_i x_i^\top$ com coeficientes e vetores não negativos. Determinar a pertinência no cone das matrizes completamente positivas ($CP_n$) é difícil; entretanto, a teoria da dualidade sugere que um certificado para $Q \notin CP_n$ é uma matriz copositiva $B$ tal que $\langle B, Q \rangle < 0$. Os autores investigam a estrutura das matrizes copositivas perfeitas para facilitar algoritmos (especificamente um algoritmo do tipo simplex de Voronoi) que possam percorrer o espaço das matrizes copositivas para encontrar tais certificados ou fatorações CP.

Metodologia
Os autores estendem a clássica teoria de redução de Voronoi, que analisa a estrutura poliédrica do poliedro de Ryshkov para matrizes positivas definidas, para o cone das matrizes copositivas ($COP_n$).

1. Definições: Eles definem o mínimo copositivo de uma matriz simétrica $B$ como $\min_{COP} B = \inf \{ B[v] : v \in \mathbb{Z}^n_{\geq 0} \setminus \{0\} \}$. Uma matriz estritamente copositiva é denominada copositiva perfeita se for unicamente determinada pelo seu mínimo copositivo e pelo conjunto de vetores inteiros não negativos que atingem este mínimo.
2. Estrutura Poliédrica: Eles definem o poliedro de Ryshkov copositivo ($R_{COP}$) como o conjunto de matrizes $B$ onde $B[v] \geq 1$ para todo $v \in \mathbb{Z}^n_{\geq 0}$ não nulo. Os vértices de $R_{COP}$ correspondem a matrizes copositivas perfeitas.
3. Travessia de Grafo: O estudo envolve a análise do grafo de vizinhança desses vértices. Matrizes copositivas perfeitas vizinhas são encontradas ao mover-se ao longo de raios extremos do dual do cone de Voronoi copositivo.
4. Análise Dimensional: O artigo conduz uma análise estrutural detalhada para baixas dimensões ($n=2$ e $n=3$) para identificar semelhanças e diferenças com a teoria clássica, e então generaliza os achados para $n \geq 3$.
5. Técnicas de Elevação (Lifting): Os autores empregam uma operação de "elevação" (Lema 5.1) para construir matrizes copositivas perfeitas de dimensões superiores a partir de outras de dimensões menores, preservando propriedades específicas como posto e mínimo copositivo.

Principais Contribuições e Resultados

*로 Diferenças da Teoria Clássica ($n \geq 3$):
* Ao contrário do caso clássico onde matrizes perfeitas são positivas definidas, matrizes copositivas perfeitas podem ser indefinidas ou semidefinidas positivas com posto estritamente menor que $n$.
* Para $n \geq 3$, existem matrizes copositivas perfeitas em todos os componentes do cone copositivo, incluindo o conjunto das matrizes copositivas excepcionais ($COP_n \setminus (S^n_{\geq 0} + N^n)$), que só existem para $n \geq 5$.
* Um novo fenômeno é identificado onde certas direções a partir de uma matriz copositiva perfeita levam a um raio extremo de $R_{COP}$ em vez de uma matriz perfeita contígua, uma situação que não ocorre na teoria clássica.
* Para $n=2$, as matrizes copositivas perfeitas são exatamente as matrizes perfeitas clássicas com entradas fora da diagonal negativas.

• Incorporação da Teoria Clássica:

  • O artigo prova que toda matriz positiva definida perfeita clássica é aritmeticamente equivalente a uma matriz copositiva perfeita (Teorema 6.1). Isso é alcançado ao mostrar que, para qualquer matriz perfeita clássica, existe uma transformação unimodular que mapeia seus vetores minimais para o ortante não negativo (a menos que pelo sinal), tornando-a perfeita copositiva.

• Decomposição e Caracterização Poliédrica:

  • Os autores estabelecem uma representação poliédrica para o poliedro de Ryshkov copositivo $R_{COP}$. Diferente do caso clássico, $R_{COP}$ não é meramente o fecho convexo de seus vértices; requer a adição de um cone gerado por matrizes $E_{ij}$ (onde $i \neq j$) para dar conta de direções ilimitadas (Teorema 7.1).
  • Eles provam que a união dos cones de Voronoi copositivos de matrizes copositivas perfeitas forma uma decomposição poliédrica do cone completamente positivo $CP_n$.

• Nova Caracterização de $CP_n$:

  • Um resultado significativo é uma nova caracterização do cone das matrizes completamente positivas. O artigo demonstra que $CP_n$ é exatamente o conjunto de matrizes não negativas que possuem um produto interno não negativo com todas as matrizes copositivas perfeitas (Corolário 7.7). Isso fornece uma descrição dual de $CP_n$ análoga a como $COP_n$ é o dual de $CP_n$.

Significância e Alegações
O artigo afirma fornecer o "primeiro estudo sistemático" de matrizes copositivas perfeitas. Sua significância reside em unir a clássica teoria de redução da teoria dos números com a moderna otimização copositiva. Ao estabelecer a estrutura poliédrica de $R_{COP}$ e a existência de matrizes copositivas perfeitas através de vários componentes do cone copositivo, os autores lançam a base teórica para a abordagem algorítmica mencionada em seu trabalho anterior [10]. Especificamente, os resultados apoiam a viabilidade de usar grafos de vizinhança de matrizes copositivas perfeitas para gerar certificados racionais para fatorações CP ou para provar a não pertinência em $CP_n$. Os autores notam modestamente que, embora encontrem infinitas matrizes copositivas perfeitas (mesmo que até equivalência), o problema de classificação permanece aberto para dimensões mais altas, de forma semelhante ao caso clássico.