Perfect Copositive Matrices

Sintesi Tecnica: Matrici Copositive Perfette

Enunciato del Problema
Il saggio affronta lo studio sistematico delle "matrici copositive perfette", una generalizzazione delle classiche matrici definite positive perfette nel contesto dell'ottimizzazione copositiva. La motivazione primaria è la soluzione algoritmica del problema di trovare certificati razionali per matrici completamente positive (CP). Una matrice $Q$ è completamente positiva se ammette una decomposizione $Q = \sum \alpha_i x_i x_i^\top$ con coefficienti e vettori non negativi. Determinare l'appartenenza al cono delle matrici completamente positive ($CP_n$) è difficile; tuttavia, la teoria della dualità suggerisce che un certificato per $Q \notin CP_n$ sia una matrice copositiva $B$ tale che $\langle B, Q \rangle < 0$. Gli autori investigano la struttura delle matrici copositive perfette per facilitare gli algoritmi (specificamente un algoritmo di tipo simplex di Voronoi) che possano attraversare lo spazio delle matrici copositive per trovare tali certificati o fattorizzazioni CP.

Metodologia
Gli autori estendono la classica teoria della riduzione di Voronoi, che analizza la struttura poliedrica del poliedro di Ryshkov per le matrici definite positive, al cono delle matrici copositive ($COP_n$).

1. Definizioni: Definiscono il minimo copositivo di una matrice simmetrica $B$ come $\min_{COP} B = \inf \{ B[v] : v \in \mathbb{Z}^n_{\geq 0} \setminus \{0\} \}$. Una matrice strettamente copositiva è definita copositiva perfetta se è unicamente determinata dal suo minimo copositivo e dall'insieme dei vettori interi non negativi che raggiungono tale minimo.
2. Struttura Poliedrica: Definiscono il poliedro di Ryshkov copositivo ($R_{COP}$) come l'insieme delle matrici $B$ dove $B[v] \geq 1$ per ogni $v \in \mathbb{Z}^n_{\geq 0}$ non nullo. I vertici di $R_{COP}$ corrispondono a matrici copositive perfette.
3. Traversata di Grafi: Lo studio comporta l'analisi del grafo di vicinato di questi vertici. Le matrici copositive perfette vicine si trovano muovendosi lungo i raggi estremi del duale del cono di Voronoi copositivo.
4. Analisi Dimensionale: Il saggio conduce un'analisi strutturale dettagliata per basse dimensioni ($n=2$ e $n=3$) per identificare somiglianze e differenze con la teoria classica, per poi generalizzare i risultati per $n \geq 3$.
5. Tecniche di Lifting: Gli autori impiegano un'operazione di "lifting" (Lemma 5.1) per costruire matrici copositive perfette di dimensione superiore a partire da quelle di dimensione inferiore, preservando proprietà specifiche come il rango e il minimo copositivo.

Contributi Chiave e Risultati

• Differenze dalla Teoria Classica ($n \geq 3$):

  • A differenza del caso classico dove le matrici perfette sono definite positive, le matrici copositive perfette possono essere ind definite o semi-definite positive con rango strettamente minore di $n$.
  • Per $n \geq 3$, esistono matrici copositive perfette in tutte le componenti del cono copositivo, inclusi le matrici copositive eccezionali ($COP_n \setminus (S^n_{\geq 0} + N^n)$), che esistono solo per $n \geq 5$.
  • Viene identificato un nuovo fenomeno in cui determinate direzioni da una matrice copositiva perfetta conducono a un raggio estremo di $R_{COP}$ piuttosto che a una matrice perfetta contigua, una situazione che non si verifica nella teoria classica.
  • Per $n=2$, le matrici copositive perfette sono esattamente le classiche matrici perfette con elementi fuori diagonale negativi.

• Embedding della Teoria Classica:

  • Il saggio dimostra che ogni matrice definita positiva perfetta è aritmeticamente equivalente a una matrice copositiva perfetta (Teorema 6.1). Ciò viene ottenuto dimostrando che per ogni matrice perfetta classica, esiste una trasformazione unimodulare che mappa i suoi vettori minimi nell'ortante non negativo (fino al segno), rendendola copositiva perfetta.

• Decomposizione Poliedrica e Caratterizzazione:

  • Gli autori stabiliscono una rappresentazione poliedrica per il poliedro di Ryshkov copositivo $R_{COP}$. A differenza del caso classico, $R_{COP}$ non è semplicemente l'involucro convesso dei suoi vertici; richiede l'aggiunta di un cono generato dalle matrici $E_{ij}$ (dove $i \neq j$) per rendere conto delle direzioni illimitate (Teorema 7.1).
  • Dimostrano che l'unione dei coni di Voronoi copositivi delle matrici copositive perfette forma una decomposizione poliedrica del cono completamente positivo $CP_n$.

• Nuova Caratterizzazione di $CP_n$:

  • Un risultato significativo è una nuova caratterizzazione del cono delle matrici completamente positive. Il saggio dimostra che $CP_n$ è esattamente l'insieme delle matrici non negative che hanno un prodotto interno non negativo con tutte le matrici copositive perfette (Corollario 7.7). Questo fornisce una descrizione duale di $CP_n$ analogamente a come $COP_n$ è il duale di $CP_n$.

Significatività e Rivendicazioni
Il saggio sostiene di fornire il "primo studio sistematico" delle matrici copositive perfette. La sua importanza risiede nel collegare la classica teoria della riduzione numerica con la moderna ottimizzazione copositiva. Stabilendo la struttura poliedrica di $R_{COP}$ e l'esistenza di matrici copositive perfette attraverso le varie componenti del cono copositivo, gli autori pongono le basi teoriche per l'approccio algoritmico menzionato nel loro lavoro precedente [10]. Nello specifico, i risultati supportano la fattibilità dell'uso dei grafi di vicinato delle matrici copositive perfette per generare certificati razionali per le fattorizzazioni CP o per provare la non appartenenza a $CP_n$. Gli autori notano con modestia che, sebbene abbiano trovato infiniti numeri di matrici copositive perfette (anche per equivalenza), il problema della classificazione rimane aperto per dimensioni più elevate, similmente al caso classico.