Perfect Copositive Matrices

Technische Samenvatting: Perfecte Copositieve Matrices

Probleemstelling
Het artikel behandelt de systematische studie van "perfecte copositieve matrices", een generalisatie van klassieke perfecte positief definitieve matrices binnen de context van copositieve optimalisatie. De primaire motivatie is de algoritmische oplossing voor het probleem van het vinden van rationale certificaten voor volledig positieve (CP) matrices. Een matrix $Q$ is volledig positief als deze een decompositie $Q = \sum \alpha_i x_i x_i^\top$ toelaat met niet-negatieve coëfficiënten en vectoren. Het bepalen van het lidmaatschap van de kegel van volledig positieve matrices ($CP_n$) is moeilijk; de dualiteitstheorie suggereert echter dat een certificaat voor $Q \notin CP_n$ een copositieve matrix $B$ is waarvoor $\langle B, Q \rangle < 0$. De auteurs onderzoeken de structuur van perfecte copositieve matrices om algoritmen (specifiek een Voronoi-achtige simplex-type algoritme) te faciliteren die de ruimte van copositieve matrices kunnen doorzoeken om dergelijke certificaten of CP-factorisaties te vinden.

Methodologie
De auteurs breiden de klassieke reductietheorie van Voronoi uit, die de polyhedrale structuur van de Ryshkov-polyeder voor positief definitieve matrices analyseert, naar de kegel van copositieve matrices ($COP_n$).

1. Definities: Ze definiëren het copositieve minimum van een symmetrische matrix $B$ als $\min_{COP} B = \inf \{ B[v] : v \in \mathbb{Z}^n_{\geq 0} \setminus \{0\} \}$. Een strikt copositieve matrix wordt een perfecte copositieve matrix genoemd als deze uniek wordt bepaald door haar copositieve minimum en de verzameling gehele niet-negatieve vectoren die dit minimum bereiken.
2. Polyhedrale Structuur: Ze definiëren de copositieve Ryshkov-polyeder ($R_{COP}$) als de verzameling matrices $B$ waar $B[v] \geq 1$ voor alle niet-nul $v \in \mathbb{Z}^n_{\geq 0}$. De hoekpunten van $R_{COP}$ komen overeen met perfecte copositieve matrices.
3. Graafdoorloop: De studie omvat het analyseren van de nabuurschapsgraaf van deze hoekpunten. Naburige perfecte copositieve matrices worden gevonden door te bewegen langs de extreme stralen van de dual van de copositieve Voronoi-kegel.
4. Dimensie-analyse: Het artikel voert een gedetailleerde structurele analyse uit voor lage dimensies ($n=2$ en $n=3$) om gelijkenissen en verschillen met de klassieke theorie te identificeren, en generaliseert vervolgens de bevindingen voor $n \geq 3$.
5. Lifting-technieken: De auteurs maken gebruik van een "lifting"-operatie (Lemma 5.1) om hogere-dimensie perfecte copositieve matrices te construeren uit lager-dimensie matrices, waarbij specifieke eigenschappen zoals rang en copositief minimum behouden blijven.

Kernbijdragen en Resultaten

• Verschillen met de Klassieke Theorie ($n \geq 3$):

  • In tegenstelling tot het klassieke geval, waar perfecte matrices positief definitief zijn, kunnen perfecte copositieve matrices indefiniet of positief semidefinitief zijn met een rang die strikt kleiner is dan $n$.
  • Voor $n \geq 3$ bestaan er perfecte copositieve matrices in alle componenten van de copositieve kegel, inclus\n bij de uitzonderlijke copositieve matrices ($COP_n \setminus (S^n_{\geq 0} + N^n)$), die pas voor $n \geq 5$ voorkomen.
  • Er wordt een nieuw fenomeen geïdentificeerd waarbij bepaalde richtingen vanaf een perfecte copositieve matrix leiden tot een extreme straal van $R_{COP}$ in plaats van een aaneengesloten perfecte matrix, een situatie die niet voorkomt in de klassieke theorie.
  • Voor $n=2$ zijn de perfecte copositieve matrices exact de klassieke perfecte matrices met negatieve off-diagonal elementen.

• Inbedding van de Klassieke Theorie:

  • Het artikel bewijst dat elke klassieke perfecte positief definitieve matrix rekenkundig equivalent is aan een perfecte copositieve matrix (Theorem 6.1). Dit wordt bereikt door aan te tonen dat voor elke klassieke perfecte matrix er een unimodulaire transformatie bestaat die haar minimale vectoren in de niet-negatieve orthant brengt (tot aan de tekenkeuze), waardoor deze perfect copositief wordt.

• Polyhedrale Decompositie en Karakterisering:

  • De auteurs vestigen een polyhedrale representatie voor de copositieve Ryshkov-polyeder $R_{COP}$. In tegenstelling tot het klassieke geval is $R_{COP}$ niet louter het convexe omhulsel van zijn hoekpunten; het vereist de toevoeging van een kegel gegenereerd door matrices $E_{ij}$ (waar $i \neq j$) om onbegrensde richtingen te accounten (Theorem 7.1).
  • Ze bewijzen dat de vereniging van copositieve Voronoi-kegels van perfecte copositieve matrices een polyhedrale decompositie vormt van de volledig positieve kegel $CP_n$.

• Nieuwe Karakterisering van $CP_n$:

  • Een belangrijk resultaat is een nieuwe karakterisering van de kegel van volledig positieve matrices. Het artikel demonstreert dat $CP_n$ exact de verzameling niet-negatieve matrices is die een niet-negatieve inwendige product hebben met alle perfecte copositieve matrices (Corollary 7.7). Dit biedt een duale beschrijving van $CP_n$ analoog aan hoe $COP_n$ de dual is van $CP_n$.

Betekenis en Claims
Het artikel claimt de "eerste systematische studie" van perfecte copositieve matrices te bieden. De betekenis ligt in het overbruggen van de klassieke getaltheoretische reductietheorie met moderne copositieve optimalisatie. Door de polyhedrale structuur van $R_{COP}$ vast te stellen en de existentie van perfecte copositieve matrices over diverse componenten van de copositieve kegel aan te tonen, leggen de auteurs de theoretische basis voor de algoritmische benadering die in hun eerdere werk [10] werd genoemd. Specifiek ondersteunen de resultaten de haalbaarheid van het gebruik van nabuurschapsgrafen van perfecte copositieve matrices om rationale certificaten voor CP-factorisaties te generen of om niet-lidmaatschap in $CP_n$ te bewijzen. De auteurs merken bescheiden op dat hoewel zij oneindig veel perfecte copositieve matrices vinden (zelfs tot aan equivalentie), het classificatieprobleem open blijft voor hogere dimensies, vergelijkbaar met het klassieke geval.