Resumen Técnico: Suma Disyuntiva de Cuadrados

Enunciado del Problema

El artículo aborda el problema fundamental de certificar la no negatividad de polinomios. Aunque un polinomio $p$ es no negativo si $p(x) \geq 0$ para todo $x \in \mathbb{R}^n$, determinar esta propiedad es generalmente NP-duro. El enfoque estándar, el método de Suma de Cuadrados (SOS), certifica la no negatividad expresando $p$ como una única identidad algebraica $p(x) = \sum q_i^2(x)$. Sin embargo, no todos los polinomios no negativos son SOS (un hecho establecido por Hilbert), y probar la no negatividad de aquellos que no lo son típicamente requiere multiplicar $p$ por un polinomio SOS de alto grado (por ejemplo, mediante la solución de Artin al 17º problema de Hilbert). Esto resulta en identidades algebraicas con grados significativamente más altos que el polinomio original, lo que conduce a Programas Semidefinidos (SDP) que crecen exponencialmente en tamaño y se vuelven computacionalmente intratables.

La pregunta central que motiva esta investigación es: ¿Puede reducirse la complejidad de una prueba basada en SOS de la no negatividad de un polinomio construyendo varias identidades algebraicas en lugar de una sola?

Metodología

Los autores introducen el concepto de Suma Disyuntiva de Cuadrados (SOS Disyuntiva). En lugar de una única identidad global, la no negatividad se certifica mediante una colección de identidades algebraicas, cada una válida en una subregión específica del dominio. Estas subregiones forman una partición (o cobertura) del espacio, definida por una disyunción algebraica.

Definiciones Centrales

1. Disyunción Algebraica: Una colección de polinomios $\mathcal{D} = \{\{q_{k,j}\}\}$ tal que la unión de las regiones $\Omega_k = \{x \mid q_{k,j}(x) \geq 0, \forall j\}$ cubre $\mathbb{R}^n$.
2. Prueba SOS Disyuntiva: Un polinomio $p$ es una SOS disyuntiva con respecto a $\mathcal{D}$ si, para cada región $\Omega_k$, existen polinomios SOS $s_{k,j}$ tales 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, el grado de los polinomios SOS $s_{k,j}$ puede mantenerse bajo (específicamente, acotado por el grado de $p$), a diferencia de las pruebas SOS globales donde el grado a menudo debe aumentar.

Marco Teórico

El artículo establece dos resultados teóricos principales, denominados Positivstellensätze Disyuntivos:

1. Positivstellensatz Disyuntivo Basado en SDP (Teorema 1):
   Para cualquier forma definida positiva $p$ de grado $d$, existe una familia explícita de disyunciones algebraicas (construidas mediante casquetes esféricos) tal que $p$ admite una prueba SOS disyuntiva donde el grado de los multiplicadores SOS es a lo sumo $d$. Esto permite una jerarquía convergente de cotas inferiores para la minimización de polinomios sobre la esfera unitaria utilizando SDPs de tamaño fijo (independiente del nivel de la jerarquía).

2. Positivstellensatz Disyuntivo Libre de Optimización (Teorema 8):
   Un resultado más fuerte que muestra que para cualquier forma definida positiva, existe una familia de disyunciones simpliciales (conos poliédricos) tal que $p$ puede certificarse como no negativa simplemente verificando que sus coeficientes sean no negativos después de un cambio de coordenadas lineal dentro de cada cono. Este enfoque requiere ningún solver de optimización (solo programación lineal o verificaciones directas de coeficientes), pero puede requerir un mayor número de regiones en comparación con el enfoque basado en SDP.

Marco Algorítmico

Los autores proponen un marco de Búsqueda Espacial por Ramificación y Acotación (SBB) para buscar adaptativamente estas pruebas disyuntivas. En lugar de particionar uniformemente el espacio (como en las pruebas teóricas), el algoritmo:

• Mantiene un árbol de subregiones (conos simpliciales).
• Calcula cotas inferiores mediante SDPs (o verificaciones lineales) en cada subregión.
• Calcula cotas superiores mediante descenso de gradiente proyectado.
• Ramifica bisecando la arista más larga de la subregión con la cota inferior más pequeña.
  Este enfoque adaptativo busca encontrar certificados con menos subregiones que las construcciones uniformes.

Contribuciones y Resultados Clave

1. Garantías Teóricas

• Grado Fijo: El artículo demuestra que siempre existen pruebas SOS disyuntivas de bajo grado. El grado de los polinomios SOS en la prueba no necesita crecer con el nivel de la jerarquía; puede fijarse en el grado del polinomio original.
• Convergencia: Los autores construyen una jerarquía de SDPs con restricciones de tamaño fijo que converge al mínimo global de un polinomio homogéneo sobre la esfera unitaria. Establecen una tasa de convergencia de $O(1/m)$, donde $m$ se relaciona con la resolución de la partición espacial.
• Certificados Libres de Optimización: El segundo Positivstellensatz proporciona un método para certificar la no negatividad sin resolver SDPs, confiando en cambio en transformaciones lineales y verificaciones de no negatividad de coeficientes.

2. Aplicación a Optimización con Restricciones

• Optimización Polinómica: Al combinar el enfoque disyuntivo con una técnica de reducción de [2], los autores construyen una jerarquía convergente de cotas inferiores para problemas generales de optimización polinómica (POPs) sobre conjuntos semialgebraicos básicos compactos.
• Programación Copositiva: El método se especializa para certificar la copositividad de matrices (verificar $x^T Q x \geq 0$ para $x \geq 0$). Los autores definen una condición "Disyuntiva P+N" donde una matriz se certifica copositiva si, en cada subregión simplicial del ortante no negativo, puede descomponerse en una matriz semidefinida positiva y una matriz no negativa. Esto produce una jerarquía completa donde el tamaño de la restricción SDP permanece fijo ($n \times n$), en contraste con jerarquías existentes donde el tamaño de la restricción crece polinomialmente con el nivel.

3. Experimentos Numéricos

Los autores presentan experimentos numéricos sobre:

• Polinomios No SOS: Los algoritmos certificaron exitosamente la no negatividad de polinomios clásicos no SOS (por ejemplo, Motzkin, Robinson, Choi-Lam, Delzell) utilizando un pequeño número de subregiones (a menudo menos de 20) mediante el marco SBB.
• Programas Copositivos: El algoritmo resolvió programas cuadráticos no convexos y calculó el número de cliques de grafos (mediante el teorema de Motzkin-Straus) en instancias aleatorias.
• Rendimiento: Los resultados indican que el enfoque disyuntivo puede certificar la no negatividad y resolver problemas de optimización con significativamente menos subregiones que la partición uniforme, y las restricciones SDP permanecen manejables en tamaño.

Significado y Afirmaciones

El artículo afirma que el enfoque de la suma disyuntiva de cuadrados ofrece una alternativa viable a las jerarquías SOS tradicionales al desacoplar la complejidad de la prueba (el grado de los polinomios SOS) del número de identidades algebraicas utilizadas.

• Eficiencia Computacional: Al mantener el grado de los polinomios SOS bajo y fijo, el tamaño de los SDPs subyacentes permanece constante a lo largo de la jerarquía, evitando la "maldición de la dimensionalidad" asociada con el aumento de los grados polinómicos en los métodos SOS estándar.
• Flexibilidad: El marco admite tanto búsquedas basadas en SDP (para cotas más ajustadas con menos regiones) como búsquedas libres de optimización (para certificados más rápidos, aunque potencialmente más gruesos).
• Completitud: Los autores demuestran que este enfoque es completo; para cualquier polinomio estrictamente positivo (o matriz estrictamente copositiva), existe un certificado dentro de su marco.

El artículo concluye señalando que, aunque las construcciones teóricas utilizan particiones uniformes, el algoritmo SBB práctico refina adaptativamente el espacio, lo que sugiere que las disyunciones específicas de la instancia podrían reducir aún más el número de regiones requeridas. El trabajo abre vías para combinar la SOS disyuntiva con la explotación de la dispersidad y la simetría, y para explorar el lado dual de momentos del marco.