Copositivity, discriminants and nonseparable signed supports

Resumen Técnico: Copositividad, Discriminantes y Soportes con Signo No Separables

Planteamiento del Problema
El artículo aborda el problema de determinar la copositividad de los signomiales —funciones definidas en el ortante real positivo $\mathbb{R}^n_{>0}$ como combinaciones lineales de monomios con exponentes reales—. Específicamente, investiga la relación entre la frontera del cono de los signomiales copositivos, los discriminantes y la estructura combinatoria del soporte con signo del signomial (el conjunto de exponentes emparejados con los signos de sus coeficientes). Si bien la no negatividad global es un tema central en la geometría algebraica real, decidir la pertenencia al cono de los polinomios copositivos es un problema NP-duro. Los métodos existentes suelen basarse en certificados de no negatividad, tales como Sumas de Cuadrados (SOS), Sumas de Circuitos No Negativos (SONC) o Sumas de Exponenciales Aritmético-Geométricas (SAGE). Una cuestión abierta clave es caracterizar los soportes con signo para los cuales todo signomial copositivo admite una descomposición SONC.

Metodología
Los autores desarrollan un criterio para la copositividad que se basa en la geometría del discriminante con signo y en métodos de continuación de homotopía.

1. Discriminantes con Signo y Caminos: Los autores definen el discriminante con signo $(A^+, A^-)$, $\nabla_{>0}(A^+, A^-)$, como el conjunto de vectores de coeficientes para los cuales el signomial (o sus truncamientos a las caras del envolvente convexo del soporte) posee un cero singular positivo. Construyen un camino específico en el espacio de coeficientes, $c(t)$, que escala los coeficientes de los términos negativos mediante un parámetro $t$ preservando los signos de los coeficientes.
2. Criterio de Intersección: La herramienta teórica central es la observación de que un signomial es copositivo si y solo si el camino $c(t)$ no intersecta el discriminante con signo para cualquier $t < 1$. El conjunto de puntos de intersección $T$ se analiza para encontrar un valor mínimo $t^*$. La copositividad es equivalente a que $t^* \geq 1$.
3. Soportes con Signo No Separables: El artículo introduce el concepto combinatorio de "soportes con signo no separables". Un par $(A^+, A^-)$ es no separable si $A^-$ está contenido dentro de una celda $D$ del refinamiento común de todas las subdivisiones poliedrales regulares de $A^+$. Esta condición geométrica generaliza casos conocidos donde se garantizan certificados SONC.
4. Continuación de Homotopía: Para soportes no separables, los autores demuestran que el conjunto $T$ contiene exactamente un elemento $t^*$. Esto permite el uso de la continuación de homotopía de parámetros para rastrear un único camino de solución desde un punto de partida conocido (donde el signomial tiene un cero singular en $x=1$) hasta el signomial objetivo, evitando la necesidad de resolver múltiples sistemas o evaluar puntos críticos directamente.

Contribuciones Clave y Resultados

• Criterio de Copositividad (Teorema A/Teorema 2.9): Los autores establecen una condición necesaria y suficiente para la copositividad. Para un signomial con soporte con signo $(A^+, A^-)$ donde $A^- \subseteq \text{conv}(A^+)$, la copositividad se cumple si y solo si el parámetro mínimo $t^*$ en el cual el camino $c(t)$ intersecta el discriminante con signo (o los discriminantes de sus truncamientos) satisface $t^* \geq 1$. Este criterio evita los errores numéricos asociados con la evaluación del signomial en puntos críticos.
• Descomposición SONC para Soportes No Separables (Teorema B/Teorema 3.16): El artículo demuestra que para cualquier soporte con signo no separable donde $A^-$ se encuentra en el interior relativo de una cara de $\text{conv}(A^+)$, el cono de los signomiales copositivos coincide con el cono SONC. En otras palabras, todo signomial copositivo con tal soporte admite una descomposición en una suma de signomiales de circuitos no negativos. Esto generaliza resultados previos que requerían condiciones geométricas específicas (por ejemplo, vértices simples).
• Unicidad y No Degeneración (Teorema C/Teorema 3.17 y 4.5): Para soportes no separables, el conjunto de intersección $T$ consiste en exactamente un punto $t^*$. Además, el sistema crítico correspondiente tiene un cero singular positivo único y no degenerado. Este resultado teórico asegura que los métodos numéricos (continuación de homotopía) sean robustos y eficientes para esta clase de problemas, ya que no sufren por la pérdida de soluciones debido a conjuntos de ceros de dimensión positiva.
• Caracterización de la Frontera (Teorema 3.18): Los autores muestran que para soportes con signo no separables, la frontera algebraica del cono de los polinomios copositivos está contenida en (y es igual a, bajo condiciones específicas, el) discriminante con signo.
• Implementación Computacional: El artículo presenta el paquete de Julia CopositivityDiscriminants.jl, que implementa estos métodos. Demuestra que para soportes no separables, rastrear un único camino de homotopía es significativamente más eficiente (segundos frente a minutos) y numéricamente estable en comparación con rastrear todos los caminos o usar certificados SAGE, particularmente para signomiales muy cercanos a la frontera del discriminante.

Significancia y Reivindicaciones
El artículo afirma proporcionar un marco unificado que conecta los discriminantes, la copositividad y las descomposiciones SONC. Su principal significancia radica en:

1. Generalización: Extiende la clase conocida de soportes con signo para los cuales la copositividad implica la descomponibilidad SONC hacia la clase más amplia de soportes no separables, eliminando suposiciones restrictivas como la existencia de vértices simples.
2. Eficiencia Algorítmica: Al demostrar que los soportes no separables producen una intersección única y no degenerada con el discriminante, los autores permiten una estrategia computacional altamente eficiente (homotopía de un solo camino) que evita la explosión combinatoria de resolver múltiples sistemas críticos.
3. Estabilidad Numérica: El método ofrece un certificado de copositividad que es más robusto que los métodos basados en evaluación o los certificados SAGE cuando se trata de signomiales cerca de la frontera del cono copositivo, como se demuestra con ejemplos donde SAGE falla ante pequeñas perturbaciones mientras que el método basado en el discriminante tiene éxito.

Los autores señalan que, si bien el método es potente para soportes no separables, enfrenta limitaciones en el caso general donde los conjuntos de ceros de los sistemas críticos pueden tener dimensiones positivas, lo que podría conducir a la pérdida de soluciones en implementaciones numéricas. Sin embargo, demuestran que para coeficientes genéricos, estas patologías no ocurren.