Over-Approximating Minimizer Sets of Constrained Convex Programs with Parametric Uncertainty via Reachability Analysis

1. Enunciato del Problema

Il documento affronta la sfida di caratterizzare l'insieme delle soluzioni ottimali (minimizzatori) per un problema di ottimizzazione fortemente convesso in cui la funzione di costo dipende da parametri incerti e limitati.

• Contesto: Nella robotica e nel controllo (ad esempio, guida autonoma, manipolazione robotica), il processo decisionale si basa spesso sull'ottimizzazione. Tuttavia, i dati che guidano queste decisioni (ad esempio, l'intenzione di altri agenti, le matrici di massa) sono incerti.
• Obiettivo: Invece di trovare una singola soluzione "robusta" che minimizzi il costo nel caso peggiore (ottimizzazione robusta standard), gli autori mirano a calcolare un'approssimazione esterna certificata (sovrastimazione) dell'intero insieme dei minimizzatori ($S^\star_\xi$) attraverso tutte le possibili realizzazioni del parametro incerto $\theta \in \Theta$.
• Sfida: I metodi esistenti, come l'analisi di sensitività o le soluzioni in forma chiusa, sono spesso o intrattabili per problemi ad alta dimensionalità o altamente conservativi (producendo limiti eccessivamente ampi), limitando la loro utilità per la pianificazione sicura a valle.

2. Metodologia

L'innovazione centrale consiste nel riformulare il problema di ottimizzazione come un problema di raggiungibilità di un sistema dinamico.

A. Discesa del Gradiente Proiettata (PGD) come Sistema Dinamico

Gli autori trattano l'algoritmo di Discesa del Gradiente Proiettata (PGD) non solo come un risolutore, ma come un sistema dinamico a tempo discreto:
$$\xi_{k+1} = \text{proj}_{S_C}(\xi_k - \alpha_k \nabla_\xi J(\xi_k, \theta))$$

• Insight Chiave: Per un parametro fisso $\theta$, la PGD converge esponenzialmente al minimizzatore unico $\xi^\star(\theta)$.
• Modellazione dell'Incertezza: Il parametro $\theta$ è trattato come uno stato iniziale costante ma sconosciuto. L'insieme di tutte le possibili traiettorie PGD che partono da un punto iniziale fisso $\xi_0$ ma variano su $\theta \in \Theta$ forma un insieme raggiungibile in avanti.
• Garanzia di Convergenza: Gli autori dimostrano che la distanza tra le iterazioni PGD al passo $k$ e l'insieme dei minimizzatori reali decade esponenzialmente con tasso $\gamma^k$. Pertanto, l'insieme raggiungibile al passo $k$, inflazionato da questo limite di errore esponenziale, fornisce un'approssimazione esterna certificata dell'insieme dei minimizzatori.

B. Sintesi a Livello di Sistema (SLS) per la Raggiungibilità

Per calcolare efficientemente questi insiemi raggiungibili (specialmente per sistemi ad alta dimensionalità), gli autori impiegano la Sintesi a Livello di Sistema (SLS):

1. Traiettoria Nominale e Dinamica dell'Errore: Definiscono una traiettoria nominale $(\hat{\xi}, \hat{\theta})$ e analizzano la dinamica dell'errore ($\Delta \xi, \Delta \theta$) tra il sistema reale e quello nominale.
2. Approssimazione Lineare Tempo-Variante (LTV): Le dinamiche non lineari della PGD sono linearizzate attorno alla traiettoria nominale. La propagazione dell'errore è modellata come un sistema LTV guidato da disturbi (errori di linearizzazione).
3. Progettazione del Feedback: Invece di passi fissi, progettano una legge di feedback affine causale sull'uscita (utilizzando SLS) per ottimizzare la sequenza dei passi $\alpha_k$. Questo feedback minimizza la propagazione dell'incertezza, risultando in limiti di insieme raggiungibile più stretti rispetto agli approcci a passo fisso.
4. Ottimizzazione: Formulano un Programma Non Lineare (NLP) per trovare le matrici di risposta del sistema che minimizzano la dimensione finale dell'insieme raggiungibile, garantendo al contempo il soddisfacimento robusto dei vincoli sui passi.

C. Gestione della Non Differenziabilità

Per problemi vincolati in cui l'operatore di proiezione $\text{proj}_{S_C}$ è non differenziabile (ad esempio, insiemi di vincoli non affini):

• Smussatura: Applicano una tecnica di smussatura basata sul campionamento. L'aggiornamento PGD non liscio è approssimato da una versione smussata $\tilde{f}$ tramite convoluzione con una distribuzione uniforme.
• Limiti di Errore: Il metodo tiene conto sia dell'errore di linearizzazione delle dinamiche smussate sia dell'errore di approssimazione tra le dinamiche reali e quelle smussate, garantendo che i limiti finali rimangano validi e certificati.

3. Contributi Chiave

1. Riformulazione Teorica: Hanno dimostrato che la sovrastimazione dell'insieme dei minimizzatori è equivalente al calcolo degli insiemi raggiungibili in avanti delle dinamiche PGD con un parametro sconosciuto, sfruttando la convergenza esponenziale della PGD per fornire limiti di errore espliciti.
2. Raggiungibilità Basata su SLS: Hanno sviluppato un quadro trattabile che utilizza SLS per calcolare insiemi raggiungibili in avanti per dinamiche PGD lisce ad alta dimensionalità, con bassa conservatività.
3. Estensione a Casi Non Lisci: Hanno esteso il quadro alle dinamiche PGD non differenziabili (comuni nell'ottimizzazione vincolata) tramite una tecnica di smussatura, derivando limiti rigorosi per l'errore di approssimazione.
4. Ottimizzazione dei Passi: Hanno dimostrato che l'ottimizzazione della sequenza dei passi tramite SLS produce limiti significativamente più stretti rispetto alle linee di base a passo fisso o all'analisi di sensitività tradizionale.

4. Risultati e Simulazioni

Gli autori hanno validato il loro metodo su tre scenari:

1. Ottimizzazione Quadratica Scalare: Un semplice problema senza vincoli in cui l'insieme reale dei minimizzatori è noto analiticamente. I limiti basati su SLS erano stretti e contenevano correttamente l'insieme reale.
2. LQR ad Alta Dimensionalità con Incertezza sull'Intenzione: Un problema di Regolatore Lineare Quadratico (LQR) a 64 dimensioni.
   • Confronto: Confrontato contro i metodi classici del Teorema della Funzione Implicita (analisi di sensitività).
   • Prestazioni: Il metodo SLS ha prodotto limiti con una larghezza massima di 0.2, mentre la linea di base di analisi di sensitività ha prodotto una larghezza di limite di ~35. Ciò evidenzia una massiccia riduzione della conservatività.
3. Ottimizzazione Quadratica Vincolata: Un problema con vincoli non affini (PGD non liscia).
   • La tecnica di smussatura ha gestito con successo la non differenziabilità. Sebbene leggermente più conservativa del caso liscio a causa dell'errore di smussatura, il metodo ha comunque fornito sovrastimazioni valide e certificate.

5. Significato

• Pianificazione Critica per la Sicurezza: Fornendo limiti stretti e certificati sull'insieme delle decisioni ottimali possibili in condizioni di incertezza, questo metodo abilita una pianificazione a valle più sicura nella robotica e nei sistemi autonomi. Evita il "pessimismo" dell'ottimizzazione robusta nel caso peggiore evitando al contempo il "rischio" di ignorare l'incertezza.
• Scalabilità: L'uso di SLS permette al metodo di scalare in modo trattabile a spazi decisionali ad alta dimensionalità (dimostrato fino a 64 dimensioni), un regime in cui la raggiungibilità basata su insiemi tradizionale o l'analisi di sensitività spesso falliscono o diventano troppo conservativi.
• Intersezione Novitosa: Il documento collega con successo la teoria dell'ottimizzazione convessa (convergenza della PGD) con la teoria del controllo (analisi di raggiungibilità e SLS), offrendo un nuovo paradigma per l'analisi di problemi di ottimizzazione parametrica.

In sintesi, questo lavoro offre un approccio matematicamente rigoroso, computazionalmente efficiente e a bassa conservatività per comprendere come l'incertezza nei parametri del problema si propaga all'insieme delle soluzioni ottimali, una capacità critica per il processo decisionale autonomo robusto.