Copositivity, discriminants and nonseparable signed supports

Technische Samenvatting: Copositiviteit, Discriminanten en Niet-scheidbare Gekleurde Ondersteuningen

Probleemstelling
Het artikel behandelt het probleem van het bepalen van de copositiviteit van signomialen—functies gedefinieerd op de positieve reële orthant $\mathbb{R}^n_{>0}$ als lineaire combinaties van monomialen met reële exponenten. Specifiek wordt het onderzoek gesteld naar de relatie tussen de grens van de kegel van copositieve signomialen, discriminanten en de combinatorische structuur van de gekleurde ondersteuning (signed support) van de signomial (de verzameling exponenten gekoppeld aan de tekens van hun coëfficiënten). Hoewel globale nietnegativiteit een centraal onderwerp is in de reële algebraïsche meetkunde, is het beslissen van het lidmaatschap van de copositieve kegel NP-zwaar. Bestaande methoden vertrouwen vaak op certificaten van nietnegativiteit, zoals Sums of Squares (SOS), Sums of Nonnegative Circuits (SONC), of Sums of Arithmetic–Geometric Exponentials (SAGE). Een belangrijke openstaande vraag is het karakteriseren van de gekleurde ondersteuningen waarvoor elke copositieve signomial een SONC-decompositie toelaat.

Methodologie
De auteurs ontwikkelen een criterium voor copositiviteit dat berust op de geometrie van de gekleurde discriminant en homotopy continuation-methoden.

1. Gekleurde Discriminanten en Paden: De auteurs definiëren de gekleurde $(A^+, A^-)$-discriminant, $\nabla_{>0}(A^+, A^-)$, als de verzameling coëfficiëntvectoren waarvoor de signomial (of zijn afkortingen naar de vlakken van de convexe hull van de ondersteuning) een positieve singuliere nul bezit. Zij construeren een specifiek pad in de coëfficiëntruimte, $c(t)$, die de coëfficiënten van de negatieve termen schaalt met een parameter $t$, terwijl de tekens van de coëfficiënten behouden blijven.
2. Doorsnijdingscriterium: Het kerninstrument van de theorie is de observatie dat een signomial copositief is dan en slechts dan als het pad $c(t)$ de gekleurde discriminant niet snijdt voor enige $t < 1$. De verzameling doorsnijdingspunten $T$ wordt geanalyseerd om een minimale waarde $t^*$ te vinden. Copositiviteit is equivalent aan $t^* \geq 1$.
3. Niet-scheidbare Gekleurde Ondersteuningen: Het artikel introduceert het combinatorische concept van "niet-scheidbare" gekleurde ondersteuningen. Een paar $(A^+, A^-)$ is niet-scheidbaar als $A^-$ binnen een cel $D$ ligt van de gemeenschappelijke verfijning van alle reguliere polyedrische onderverdelingen van $A^+$. Deze geometrische voorwaarde generaliseert eerder bekende gevallen waar SONC-certificaten gegarandeerd zijn.
4. Homotopy Continuation: Voor niet-scheidbare ondersteuningen bewijzen de auteurs dat de verzameling $T$ precies één element bevat, $t^*$. Dit maakt het gebruik van parameter homotopy continuation mogelijk om een enkel oplossingstraject te volgen van een bekend startpunt (waar de signomial een singuliere nul heeft bij $x=1$) naar de doel-signomial, waardoor het nodig is om geen meerdere systemen op te lossen of kritische punten direct te evalueren.

Belangrijkste Bijdragen en Resultaten

• Copositiviteitscriterium (Theorem A/Theorem 2.9): De auteurs stellen een noodzakelijke en voldoende voorwaarde voor copositiviteit vast. Voor een signomial met gekleurde ondersteuning $(A^+, A^-)$ waar $A^- \subseteq \text{conv}(A^+)$, geldt copositiviteit dan en slechts dan als de minimale parameter $t^*$ waarbij het pad $c(t)$ de gekleurde discriminant (of de discriminanten van zijn afkortingen) snijdt, voldoet aan $t^* \geq 1$. Dit criterium vermijdt de numerieke fouten die gepaard gaan met het evalueren van de signomial in kritische punten.
• SONC-decompositie voor Niet-scheidbare Ondersteuningen (Theorem B/Theorem 3.16): Het artikel bewijst dat voor elke niet-scheidbare gekleurde ondersteuning waar $A^-$ in het relatieve binnenste van een vlak van $\text{conv}(A^+)$ ligt, de kegel van copositieve signomialen samenvalt met de SONC-kegel. Met andere woorden, elke copositieve signomial met een dergelijke ondersteuning laat zich decomponeren in een som van nietnegatieve circuit-signomialen. Dit generaliseert eerdere resultaten die specifieke geometrische voorwaarden vereisten (bijv. eenvoudige vertices).
• Uniciteit en Niet-degeneratie (Theorem C/Theorem 3.17 & 4.5): Voor niet-scheidbare ondersteuningen bestaat de doorsnijdingsverzameling $T$ uit precies één punt $t^*$. Bovendien heeft het bijbehorende kritische systeem een unieke, niet-degeneratieve positieve singuliere nul. Dit theoretische resultaat garandeert dat numerieke methoden (homotopy continuation) robuust en efficiënt zijn voor deze klasse problemen, omdat ze geen problemen ondervinden met het missen van oplossingen door positie-dimensionale nulverzamelingen.
• Grens-karakterisering (Theorem 3.18): De auteurs tonen aan dat voor niet-scheidbare ondersteuningen de algebraïsche grens van de kegel van copositieve polynomen gecontineerd is in (en gelijk is aan, onder specifieke voorwaarden, de) gekleurde discriminant.
• Computationele Implementatie: Het artikel presenteert de Julia-package CopositivityDiscriminants.jl, die deze methoden implementeert. Het demonstreert dat voor niet-scheidbare ondersteuningen het volgen van een enkel homotopy-pad aanzienlijk efficiënter (seconden versus minuten) en numeriek stabieler is vergeleken met het volgen van alle paden of het gebruiken van SAGE-certificaten, vooral voor signomialen die zeer dicht bij de discriminant-grens liggen.

Betekenis en Claims
Het artikel claimt een verenigd kader te bieden dat discriminanten, copositiviteit en SONC-decomposities verbindt. De primaire betekenis ligt in:

1. Generalisatie: Het breidt de bekende klasse van gekleurde ondersteuningen waarvoor copositiviteit SONC-decomponeerbaarheid impliceert uit naar de bredere klasse van niet-scheidbare ondersteuningen, waarbij restrictieve aannames zoals de aanwezigheid van eenvoudige vertices worden verwijderd.
2. Algoritmische Efficiëntie: Door te bewijzen dat niet-scheidbare ondersteuningen een unieke, niet-degeneratieve doorsnede met de discriminant opleveren, maken de auteurs een zeer efficiënte computationele strategie mogelijk (single-path homotopy) die de combinatorische explosie van het oplossen van meerdere kritische systemen vermijdt.
3. Numerieke Stabiliteit: De methode biedt een certificaat van copositiviteit dat robuuster is dan evaluatie-gebaseerde methoden of SAGE-certificaten wanneer men te maken heeft met signomialen nabij de grens van de copositieve kegel, zoals aangetoond door voorbeelden waar SAGE faalt bij kleine perturbaties terwijl de discriminant-gebaseerde methode slaagt.

De auteurs merken op dat hoewel de methode krachtig is voor niet-scheidbare ondersteuningen, deze beperkingen ondervindt in het algemene geval waar de nulverzamelingen van kritische systemen positieve dimensies kunnen hebben, wat potentieel kan leiden tot het missen van oplossingen in numerieke implementaties. Ze tonen echter aan dat voor generieke coëfficiënten deze pathologieën niet voorkomen.