Inclusion conditions for the Constrained Polynomial Zonotopic case

Titolo: Condizioni di Inclusione per Zonotopi Polinomiali Vincolati (CPZ)

1. Il Problema

Le rappresentazioni basate su insiemi sono fondamentali nell'analisi di raggiungibilità e nel rilevamento di guasti. Mentre gli insiemi convessi (come zonotopi ed ellissoidi) sono ben compresi e computazionalmente efficienti, la gestione di geometrie non convesse rimane una sfida significativa a causa della perdita di proprietà strutturali nelle loro rappresentazioni.
I Zonotopi Polinomiali Vincolati (CPZ) offrono un compromesso efficace: possono catturare geometrie complesse e tipicamente non convesse mantenendo una struttura algebrica manipolabile. Tuttavia, l'aumento della complessità descrittiva (maggior numero di generatori e dimensioni matriciali) rende il controllo di inclusione tra insiemi (verificare se un insieme $P_1$ è contenuto in $P_2$) un compito cruciale ma difficile. Le condizioni lineari esistenti per zonotopi vincolati (CZ) non sono sufficienti per il caso polinomiale non lineare, e le approcci attuali (es. toolbox CORA) possono fallire nel rilevare inclusioni reali a causa di pre-elaborazioni che gonfiano gli insiemi.

2. Metodologia

Gli autori propongono nuove codifiche non lineari per testare l'inclusione tra due CPZ. La metodologia si basa su una serie di passaggi logici e matematici:

• Definizione del Problema: Si considerano due insiemi CPZ, $P_1$ e $P_2$, definiti da generatori, vincoli di uguaglianza e vincoli polinomiali. L'obiettivo è trovare condizioni sufficienti affinché $P_1 \subseteq P_2$.
• Derivazione delle Condizioni (Proposizione 1):
  • Si assume che ogni punto in $P_1$ possa essere espresso come combinazione di generatori di $P_2$ tramite trasformazioni lineari e non lineari.
  • Vengono introdotte matrici di trasformazione ($\gamma, \Gamma, \Pi, \Psi, \psi$) che collegano i parametri di $P_1$ a quelli di $P_2$.
  • Utilizzando la disuguaglianza triangolare e le proprietà del logaritmo, si derivano condizioni che garantiscono che i parametri di $P_2$ rimangano entro i limiti ammissibili ($\|\lambda_2\|_\infty \le 1$).
  • Le condizioni finali (equazioni 3a-3f) includono relazioni lineari per i vincoli di uguaglianza e relazioni non lineari (coinvolgenti logaritmi e valori assoluti) per gestire i vincoli di disuguaglianza e la struttura polinomiale.
• Adattamento per l'Ottimizzazione (Corollario 1):
  • L'uso diretto dell'operatore valore assoluto ($|\cdot|$) è problematico per l'integrazione in framework di ottimizzazione standard.
  • Gli autori riformulano le condizioni non lineari introducendo variabili ausiliarie ($\alpha_\Gamma, \alpha_\Psi$) e vincoli di convessità basati sulla rappresentazione dei vertici dell'iperspazio (cross-polytope).
  • Questa riformulazione elimina l'operatore valore assoluto esplicito, mantenendo la non linearità solo tramite l'operatore logaritmico, rendendo il problema più gestibile per i solver di ottimizzazione.
• Riduzione al Caso Lineare (Corollario 2): Viene dimostrato che quando i polinomi diventano lineari (caso dei Zonotopi Vincolati - CZ), le nuove condizioni si riducono alle forme lineari note nella letteratura precedente, confermando la coerenza del metodo.

3. Contributi Chiave

1. Nuove Condizioni di Inclusione: Introduzione di condizioni sufficienti non lineari specifiche per l'inclusione tra CPZ, colmando un vuoto nella letteratura esistente che si limitava a casi lineari o convessi.
2. Formulazione per l'Ottimizzazione: Sviluppo di una riformulazione (Corollario 1) che evita l'uso esplicito dell'operatore valore assoluto, facilitando l'integrazione diretta in problemi di ottimizzazione (es. calcolo di insiemi invarianti massimali).
3. Generalità: Il metodo è generale e include come casi particolari i Zonotopi (Z), i Zonotopi Vincolati (CZ) e i Zonotopi Polinomiali (PZ).
4. Validazione Empirica: Confronto diretto con lo stato dell'arte (toolbox CORA) su casi di test specifici.

4. Risultati

I risultati sono stati validati attraverso simulazioni su tre insiemi CPZ con diverse scale di generatori e vincoli:

• Accuratezza: Il metodo proposto ha mostrato nessun falso positivo e nessun falso negativo nei test di inclusione. Ha correttamente identificato sia le inclusioni vere che le non-inclusioni.
• Confronto con CORA: Il toolbox CORA, che utilizza un approccio di sovrapprossimazione polinomiale, ha fallito nel rilevare inclusioni reali (ha restituito "falso" anche quando l'inclusione era vera, probabilmente a causa dell'espansione degli insiemi durante la pre-elaborazione).
• Efficienza Computazionale:
  • Il metodo proposto è significativamente più veloce: i tempi di calcolo sono variati tra 0.58s e 1.34s.
  • Al contrario, il metodo CORA ha richiesto tra 9.15s e 10.97s, con la maggior parte del tempo speso nella fase di pre-elaborazione e non nel test effettivo.
• Implementazione: Il codice MATLAB è stato reso pubblico su un repository GitLab.

5. Significato

Questo lavoro è significativo per la comunità del controllo e dell'analisi di sistemi perché:

• Abilita l'analisi di sistemi non lineari: Fornisce gli strumenti matematici per gestire insiemi non convessi complessi in modo rigoroso, superando i limiti degli approcci puramente convessi.
• Migliora l'efficienza: Offre un metodo di verifica dell'inclusione più rapido e affidabile rispetto alle soluzioni attuali basate su sovrapprossimazioni.
• Fondamento per applicazioni future: Le condizioni di inclusione sono un prerequisito essenziale per calcolare insiemi invarianti positivi massimali (MPI) in contesti di sistemi vincolati e non lineari, un obiettivo dichiarato per i lavori futuri degli autori. Questo apre la strada a strategie di controllo più robuste e meno conservative per sistemi dinamici complessi.