On maximal positive invariant set computation for rank-deficient linear systems

Titolo

Calcolo dell'insieme massimale positivamente invariante per sistemi lineari a rango deficiente

1. Il Problema

Il calcolo dell'insieme massimale positivamente invariante (MPI, Maximal Positively Invariant set) è fondamentale nella teoria del controllo vincolato, in particolare per garantire la ricorsività della fattibilità e la stabilità nel Controllo Predittivo a Modello (MPC). L'MPI rappresenta il più grande insieme di stati da cui il sistema può essere mantenuto all'interno dei vincoli di stato e di input indefinitamente.

Il problema specifico affrontato in questo lavoro sorge quando la sintesi del controllo a retroazione statica (ad esempio, tramite equazioni di Riccati o assegnazione dei poli) porta a un sistema a ciclo chiuso con autovalori nulli.

• Causa: Strategie di controllo ottimali o "dead-beat" possono posizionare uno o più autovalori della matrice di stato a ciclo chiuso ($A_\circ = A + BK$) nell'origine.
• Conseguenza: La matrice $A_\circ$ diventa a rango deficiente (singolare).
• Impatto sul calcolo: I metodi standard per il calcolo dell'MPI si basano su una ricorrenza di insiemi che coinvolge l'inverso della dinamica o potenze della matrice $A_\circ^k$. Quando $A_\circ$ è singolare, la dinamica proietta lo stato su sottospazi a dimensione inferiore. Questo rende i calcoli intermedi instabili o errati se non gestiti esplicitamente, poiché la mappatura non è più biettiva e gli insiemi intermedi possono degenerare o diventare illimitati lungo le direzioni degli autovalori nulli.

2. Metodologia

Gli autori propongono un algoritmo robusto che sfrutta la decomposizione di Schur reale per gestire esplicitamente la singolarità della matrice di stato.

A. Decomposizione e Struttura

La matrice a ciclo chiuso $A_\circ$ viene decomposta nella sua forma di Schur reale:
$$A_\circ = U S U^\top$$
dove $U$ è una matrice ortogonale e $S$ è una matrice triangolare superiore a blocchi. La struttura di $S$ viene organizzata per isolare gli autovalori nulli:
$$S = \begin{bmatrix} S_{11} & S_{12} \\ 0 & S_{22} \end{bmatrix}$$

• $S_{11}$: Contiene gli autovalori non nulli (dimensione $d_1$).
• $S_{22}$: Contiene gli autovalori nulli ed è nilpotente di grado $p+1$ (dimensione $d_2$).

B. Strategia di Calcolo

L'idea centrale è separare il calcolo in due fasi:

1. Riduzione: Si calcola l'MPI in un sottospazio ridotto di dimensione $d_1$ (corrispondente agli autovalori non nulli), dove la dinamica è ben comportata e non singolare.
2. Sollevamento e Intersezione: Il risultato ridotto viene "sollevato" nello spazio originale di dimensione $n$ e intersecato con i vincoli derivanti dalle prime $p$ iterazioni (dove la dinamica nilpotente ha ancora effetto).

C. Rappresentazioni Geometriche

L'algoritmo è stato sviluppato e implementato per due rappresentazioni di insiemi:

1. Politopi (Polyhedral): Rappresentazione tramite disuguaglianze lineari ($Fx \leq \theta$).
2. Zono-topi Vincolati (Constrained Zonotopes - CZ): Una rappresentazione più compatta che include vincoli di uguaglianza lineari, permettendo operazioni algebriche efficienti e chiusure sotto intersezione.

L'algoritmo (Algoritmo 1 nel paper) segue questi passi:

1. Calcolo della forma di Schur ordinata.
2. Calcolo dell'MPI ridotto $\Phi_z$ per la dinamica $z_{k+1} = S_{11}z_k$.
3. Calcolo degli insiemi ausiliari $\Phi_x^{[1]}$ (vincoli per $k < p$) e $\Phi_x^{[2]}$ (vincoli per $k \geq p$ sollevati dallo spazio ridotto).
4. Intersezione finale: $\Phi_x = \Phi_x^{[1]} \cap \Phi_x^{[2]}$.

3. Contributi Chiave

• Gestione Esplicita della Singolarità: Il primo lavoro che tratta sistematicamente il calcolo dell'MPI per sistemi lineari con autovalori nulli multipli, evitando l'instabilità numerica dei metodi standard.
• Dualità di Rappresentazione: Fornisce una soluzione valida sia per la rappresentazione politopica che per quella a zono-topi vincolati, dimostrando l'equivalenza geometrica dei risultati ottenuti con entrambi i metodi.
• Efficienza Computazionale: L'approccio riduce drasticamente la complessità computazionale per sistemi ad alta dimensionalità con rango deficiente, evitando l'esplosione del numero di iterazioni e di vincoli tipica dei metodi standard.
• Algoritmo Generale: La metodologia è indipendente dal numero di autovalori nulli e dalla loro molteplicità (struttura dei blocchi di Jordan).

4. Risultati Sperimentali

Gli autori hanno validato l'approccio su due esempi:

1. Esempio Numerico in $\mathbb{R}^6$: Un sistema con una matrice a ciclo chiuso che possiede blocchi di Jordan di dimensioni 1 e 2 per l'autovalore zero.
   • Il calcolo dell'MPI ridotto in $\mathbb{R}^3$ è stato completato in 3 iterazioni.
   • Il tempo totale di calcolo è stato di 0.4 secondi, dimostrando la fattibilità pratica.
2. Esperimento con Molle Accoppiate (CSE): Un sistema fisico con massa variabile ($\ell$ masse), che porta a dimensioni dello stato fino a $2\ell$.
   • Confronto: L'algoritmo proposto è stato confrontato con il metodo standard (senza gestione della singolarità).
   • Scalabilità: Per dimensioni elevate ($\ell \geq 8$, stato in $\mathbb{R}^{16}$), il metodo standard richiede un numero di iterazioni esponenzialmente crescente e tempi di calcolo proibitivi.
   • Efficienza: Il metodo proposto mantiene un numero di iterazioni moderato e tempi di calcolo bassi anche per dimensioni elevate.
   • Complessità dei Vincoli: Il metodo standard genera un numero enorme di disuguaglianze (es. 1496 per $\ell=10$), mentre il metodo rank-deficient riduce significativamente questo numero (es. 704 per $\ell=10$), mantenendo una rappresentazione più compatta.

5. Significato e Implicazioni

Questo lavoro risolve una lacuna critica nella teoria del controllo vincolato. Poiché molte sintesi di controllo ottimali (come quelle basate su Riccati) tendono naturalmente a posizionare autovalori all'origine per massimizzare la velocità di convergenza o minimizzare l'energia, la capacità di calcolare correttamente l'MPI per questi sistemi è essenziale per l'implementazione sicura dell'MPC.

L'approccio proposto:

• Garantisce la sicurezza: Permette di definire correttamente l'insieme terminale nell'MPC anche per sistemi singolari, prevenendo la perdita di fattibilità ricorsiva.
• Abilita l'uso di sistemi complessi: Rende fattibile il controllo predittivo per sistemi ad alta dimensionalità che altrimenti richiederebbero risorse computazionali eccessive.
• Fornisce un framework estendibile: La struttura basata sulla decomposizione di Schur apre la strada a future applicazioni su insiemi massimali ammissibili in uscita (MOAS) e altre varianti di problemi di raggiungibilità.

In sintesi, il paper offre un algoritmo matematicamente rigoroso e computazionalmente efficiente per un problema geometrico complesso, rendendo il controllo predittivo più robusto e applicabile a una classe più ampia di sistemi dinamici.