Perfect Copositive Matrices

Resumen Técnico: Matrices Copositivas Perfectas

Planteamiento del Problema
El artículo aborda el estudio sistemático de las "matrices copositivas perfectas", una generalización de las matrices clásicas de definición positiva perfecta dentro del contexto de la optimización copositiva. La motivación principal es la solución algorítmica al problema de encontrar certificados racionales para matrices completamente positivas (CP). Una matriz $Q$ es completamente positiva si admite una descomposición $Q = \sum \alpha_i x_i x_i^\top$ con coeficientes y vectores no negativos. Determinar la pertenencia al cono de las matrices completamente positivas ($CP_n$) es difícil; sin embargo, la teoría de la dualidad sugiere que un certificado para $Q \notin CP_n$ es una matriz copositiva $B$ tal que $\langle B, Q \rangle < 0$. Los autores investigan la estructura de las matrices copositivas perfectas para facilitar algoritmos (específicamente un algoritmo de tipo simplex de Voronoi) que puedan recorrer el espacio de las matrices copositivas para encontrar tales certificados o factorizaciones CP.

Metodología
Los autores extienden la clásica teoría de reducción de Voronoi, que analiza la estructura poliédrica del poliedro de Ryshkov para matrices de definición positiva, al cono de las matrices copositivas ($COP_n$).

1. Definiciones: Definen el mínimo copositivo de una matriz simétrica $B$ como $\min_{COP} B = \inf \{ B[v] : v \in \mathbb{Z}^n_{\geq 0} \setminus \{0\} \}$. Una matriz estrictamente copositiva se denomina copositiva perfecta si está determinada de forma única por su mínimo copositivo y el conjunto de vectores enteros no negativos que alcanzan dicho mínimo.
2. Estructura Poliédrica: Definen el poliedro de Ryshkov copositivo ($R_{COP}$) como el conjunto de matrices $B$ donde $B[v] \geq 1$ para todo $v \in \mathbb{Z}^n_{\geq 0}$ no nulo. Los vértices de $R_{COP}$ corresponden a matrices copositivas perfectas.
3. Recorrido de Grafos: El estudio implica el análisis del grafo de vecindad de estos vértices. Las matrices copositivas perfectas vecinas se encuentran moviéndose a lo largo de los rayos extremos del dual del cono de Voronoi copositivo.
4. Análisis Dimensional: El artículo realiza un análisis estructural detallado para dimensiones bajas ($n=2$ y $n=3$) para identificar similitudes y diferencias con la teoría clásica, y luego generaliza los hallazgos para $n \geq 3$.
5. Técnicas de Elevación (Lifting): Los autores emplean una operación de "elevación" (Lema 5.1) para construir matrices copositivas perfectas de mayor dimensión a partir de otras de menor dimensión, preservando propiedades específicas como el rango y el mínimo copositivo.

Contribuciones Clave y Resultados

• Diferencias con la Teoría Clásica ($n \geq 3$):

  • A diferencia del caso clásico donde las matrices perfectas son de definición positiva, las matrices copositivas perfectas pueden ser indefinidas o semidefinidas positivas con un rango estrictamente menor que $n$.
  • Para $n \geq 3$, existen matrices copositivas perfectas en todos los componentes del cono copositivo, incluyendo el conjunto de matrices copositivas excepcionales ($COP_n \setminus (S^n_{\geq 0} + N^n)$), que solo existen para $n \geq 5$.
  • Se identifica un nuevo fenómeno donde ciertas direcciones desde una matriz copositiva perfecta conducen a un rayo extremo de $R_{COP}$ en lugar de a una matriz perfecta contigua, una situación que no ocurre en la teoría clásica.
  • Para $n=2$, las matrices copositivas perfectas son exactamente las matrices perfectas clásicas con entradas fuera de la diagonal negativas.

• Incrustación de la Teoría Clásica:

  • El artículo demuestra que toda matriz clásica de definición positiva perfecta es aritméticamente equivalente a una matriz copositiva perfecta (Teorema 6.1). Esto se logra mostrando que para cualquier matriz perfecta clásica, existe una transformación unimodular que mapea sus vectores mínimos en el ortante no negativo (salvo el signo), convirtiéndola así en perfecta copositiva.

• Descomposición y Caracterización Poliédrica:

  • Los autores establecen una representación poliédrica para el poliedro de Ryshkov copositivo $R_{COP}$. A diferencia del caso clásico, $R_{COP}$ no es meramente la envolvente convexa de sus vértices; requiere la adición de un cono generado por matrices $E_{ij}$ (donde $i \neq j$) para dar cuenta de las direcciones no acotadas (Teorema 7.1).
  • Demuestran que la unión de los conos de Voronoi copositivos de las matrices copositivas perfectas forma una descomposición poliédrica del cono completamente positivo $CP_n$.

• Nueva Caracterización de $CP_n$:

  • Un resultado significativo es una nueva caracterización del cono de las matrices completamente positivas. El artículo demuestra que $CP_n$ es exactamente el conjunto de matrices no negativas que tienen un producto interno no negativo con todas las matrices copositivas perfectas (Corolario 7.7). Esto proporciona una descripción dual de $CP_n$ análoga a cómo $COP_n$ es el dual de $CP_n$.

Significancia y Pretensiones
El artículo afirma proporcionar el "primer estudio sistemático" de las matrices copositivas perfectas. Su importancia radica en tender un puente entre la clásica teoría de reducción número-teórica y la optimización copositiva moderna. Al establecer la estructura poliédrica de $R_{COP}$ y la existencia de matrices copositivas perfectas a través de varios componentes del cono copositivo, los autores sientan las bases teóricas para el enfoque algorítmico mencionado en su trabajo previo [10]. Específicamente, los resultados respaldan la viabilidad de utilizar los grafos de vecindad de las matrices copositivas perfectas para generar certificados racionales para factorizaciones CP o para probar la no pertenencia en $CP_n$. Los autores señalan modestamente que, aunque encuentran infinitas matrices copositivas perfectas (incluso bajo equivalencia), el problema de la clasificación sigue abierto para dimensiones superiores, de manera similar al caso clásico.