Riepilogo Tecnico: Somma Disgiuntiva di Quadrati

Enunciato del Problema

Il lavoro affronta il problema fondamentale di certificare la non negatività dei polinomi. Mentre un polinomio $p$ è non negativo se $p(x) \geq 0$ per ogni $x \in \mathbb{R}^n$, determinare questa proprietà è generalmente NP-difficile. L'approccio standard, il metodo della Somma di Quadrati (SOS), certifica la non negatività esprimendo $p$ come una singola identità algebrica $p(x) = \sum q_i^2(x)$. Tuttavia, non tutti i polinomi non negativi sono SOS (un fatto stabilito da Hilbert), e dimostrare la non negatività per quelli che non lo sono richiede tipicamente moltiplicare $p$ per un polinomio SOS di alto grado (ad esempio, tramite la soluzione di Hilbert al 17° problema di Hilbert). Ciò risulta in identità algebriche con gradi significativamente più alti rispetto al polinomio originale, portando a Programmi Semidefiniti (SDP) che crescono esponenzialmente di dimensioni e diventano computazionalmente intrattabili.

La domanda centrale che motiva questa ricerca è: È possibile ridurre la complessità di una dimostrazione basata su SOS della non negatività di un polinomio costruendo diverse identità algebriche invece di una singola?

Metodologia

Gli autori introducono il concetto di Somma Disgiuntiva di Quadrati (Disjunctive SOS). Invece di una singola identità globale, la non negatività è certificata da una collezione di identità algebriche, ciascuna valida su una specifica sotto-regione del dominio. Queste sotto-regioni formano una partizione (o una copertura) dello spazio, definita da una disgiunzione algebrica.

Definizioni Fondamentali

1. Disgiunzione Algebrica: Una collezione di polinomi $\mathcal{D} = \{\{q_{k,j}\}\}$ tale che l'unione delle regioni $\Omega_k = \{x \mid q_{k,j}(x) \geq 0, \forall j\}$ copre $\mathbb{R}^n$.
2. Dimostrazione SOS Disgiuntiva: Un polinomio $p$ è una SOS disgiuntiva rispetto a $\mathcal{D}$ se, per ogni regione $\Omega_k$, esistono polinomi SOS $s_{k,j}$ tali che:
   $$p(x) = s_{k,0}(x) + \sum_{j=1}^{n_k} s_{k,j}(x)q_{k,j}(x) \quad \text{per ogni } x \in \Omega_k.$$
   Crucialmente, il grado dei polinomi SOS $s_{k,j}$ può essere mantenuto basso (specificamente, limitato dal grado di $p$), a differenza delle dimostrazioni SOS globali dove il grado deve spesso aumentare.

Quadro Teorico

Il lavoro stabilisce due principali risultati teorici, denominati Positivstellensatz Disgiuntivi:

1. Positivstellensatz Disgiuntivo basato su SDP (Teorema 1):
   Per ogni forma definita positiva $p$ di grado $d$, esiste una famiglia esplicita di disgiunzioni algebriche (costruite tramite calotte sferiche) tale che $p$ ammette una dimostrazione SOS disgiuntiva dove il grado dei moltiplicatori SOS è al massimo $d$. Ciò permette una gerarchia convergente di limiti inferiori per la minimizzazione di polinomi sulla sfera unitaria utilizzando SDP di dimensione fissa (indipendente dal livello della gerarchia).

2. Positivstellensatz Disgiuntivo senza Ottimizzazione (Teorema 8):
   Un risultato più forte che mostra come per ogni forma definita positiva esista una famiglia di disgiunzioni simpliciali (coni poliedrici) tale che $p$ possa essere certificata come non negativa semplicemente verificando che i suoi coefficienti siano non negativi dopo un cambiamento di coordinate lineare all'interno di ciascun cono. Questo approccio richiede nessun solver di ottimizzazione (solo programmazione lineare o verifiche dirette dei coefficienti) ma può richiedere un numero maggiore di regioni rispetto all'approccio basato su SDP.

Quadro Algoritmico

Gli autori propongono un quadro Spatial Branch-and-Bound (SBB) per cercare adattivamente queste dimostrazioni disgiuntive. Piuttosto che partizionare uniformemente lo spazio (come nelle dimostrazioni teoriche), l'algoritmo:

• Mantiene un albero di sotto-regioni (coni simpliciali).
• Calcola limiti inferiori tramite SDP (o verifiche lineari) su ciascuna sotto-regione.
• Calcola limiti superiori tramite discesa del gradiente proiettata.
• Dirama bisecando il lato più lungo della sotto-regione con il limite inferiore più piccolo.
  Questo approccio adattivo mira a trovare certificati con meno sotto-regioni rispetto alle costruzioni uniformi.

Contributi e Risultati Chiave

1. Garanzie Teoriche

• Grado Fisso: Il lavoro dimostra che dimostrazioni SOS disgiuntive a basso grado esistono sempre. Il grado dei polinomi SOS nella dimostrazione non deve crescere con il livello della gerarchia; può essere fissato al grado del polinomio originale.
• Convergenza: Gli autori costruiscono una gerarchia di SDP con vincoli di dimensione fissa che converge al minimo globale di un polinomio omogeneo sulla sfera unitaria. Stabiliscono un tasso di convergenza di $O(1/m)$, dove $m$ è correlato alla risoluzione della partizione spaziale.
• Certificati senza Ottimizzazione: Il secondo Positivstellensatz fornisce un metodo per certificare la non negatività senza risolvere SDP, affidandosi invece a trasformazioni lineari e verifiche di non negatività dei coefficienti.

2. Applicazione all'Ottimizzazione Vincolata

• Ottimizzazione Polinomiale: Combinando l'approccio disgiuntivo con una tecnica di riduzione da [2], gli autori costruiscono una gerarchia convergente di limiti inferiori per problemi generali di ottimizzazione polinomiale (POPs) su insiemi semialgebrici compatti di base.
• Programmazione Copositiva: Il metodo è specializzato per certificare la copositività delle matrici (verificare $x^T Q x \geq 0$ per $x \geq 0$). Gli autori definiscono una condizione "Disgiuntiva P+N" dove una matrice è certificata copositiva se, su ciascuna sotto-regione simpliciale del ortante non negativo, può essere decomposta in una matrice semidefinita positiva e una matrice non negativa. Ciò produce una gerarchia completa dove la dimensione del vincolo SDP rimane fissa ($n \times n$), in contrasto con le gerarchie esistenti dove la dimensione del vincolo cresce polinomialmente con il livello.

3. Esperimenti Numerici

Gli autori presentano esperimenti numerici su:

• Polinomi non SOS: Gli algoritmi hanno certificato con successo la non negatività di classici polinomi non SOS (ad esempio, Motzkin, Robinson, Choi-Lam, Delzell) utilizzando un piccolo numero di sotto-regioni (spesso meno di 20) tramite il quadro SBB.
• Programmi Copositivi: L'algoritmo ha risolto programmi quadratici non convessi e calcolato il numero di clique di grafi (tramite il teorema di Motzkin-Straus) su istanze casuali.
• Prestazioni: I risultati indicano che l'approccio disgiuntivo può certificare la non negatività e risolvere problemi di ottimizzazione con significativamente meno sotto-regioni rispetto al partizionamento uniforme, e i vincoli SDP rimangono gestibili in termini di dimensioni.

Significato e Affermazioni

Il lavoro afferma che l'approccio della somma disgiuntiva di quadrati offre un'alternativa praticabile alle gerarchie SOS tradizionali, disaccoppiando la complessità della dimostrazione (il grado dei polinomi SOS) dal numero di identità algebriche utilizzate.

• Efficienza Computazionale: Mantenendo il grado dei polinomi SOS basso e fisso, la dimensione degli SDP sottostanti rimane costante lungo tutta la gerarchia, evitando la "maledizione della dimensionalità" associata all'aumento dei gradi polinomiali nei metodi SOS standard.
• Flessibilità: Il quadro supporta sia ricerche basate su SDP (per limiti più stretti con meno regioni) sia ricerche senza ottimizzazione (per certificati più rapidi, sebbene potenzialmente più grossolani).
• Completezza: Gli autori dimostrano che questo approccio è completo; per ogni polinomio strettamente positivo (o matrice strettamente copositiva), esiste un certificato all'interno del loro quadro.

Il lavoro conclude notando che, mentre le costruzioni teoriche utilizzano partizioni uniformi, l'algoritmo pratico SBB affina adattivamente lo spazio, suggerendo che disgiunzioni specifiche per istanza potrebbero ridurre ulteriormente il numero di regioni richieste. Il lavoro apre la strada alla combinazione della SOS disgiuntiva con lo sfruttamento della sparsità e della simmetria, e all'esplorazione del lato dei momenti duale del quadro.