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

1. Probleemstelling

Het artikel adresseert de uitdaging om de verzameling van optimale oplossingen (minima) te karakteriseren voor een sterk convex optimalisatieprobleem waarbij de kostenfunctie afhankelijk is van onzekere, begrenste parameters.

• Context: In robotica en besturing (bijvoorbeeld autonoom rijden, robotmanipulatie) berust besluitvorming vaak op optimalisatie. De data die deze beslissingen stuurt (bijvoorbeeld de intentie van andere agenten, massamatrices) is echter onzeker.
• Doel: In plaats van een enkele "robuste" oplossing te vinden die de worst-case kosten minimaliseert (standaard robuuste optimalisatie), streven de auteurs ernaar een gecertificeerde buitenbenadering (over-approximation) te berekenen van de hele verzameling van minima ($S^\star_\xi$) over alle mogelijke realisaties van de onzekere parameter $\theta \in \Theta$.
• Uitdaging: Bestaande methoden, zoals gevoeligheidsanalyse of gesloten-vorm oplossingen, zijn vaak ofwel onhandelbaar voor hoog-dimensionale problemen, of uiterst conservatief (ze produceren overmatig grote grenzen), wat hun bruikbaarheid beperkt voor downstream veiligheidsplanning.

2. Methodologie

De kerninnovatie is het herformuleren van het optimalisatieprobleem als een bereikbaarheidsprobleem voor dynamische systemen.

A. Projected Gradient Descent (PGD) als Dynamisch Systeem

De auteurs behandelen het Projected Gradient Descent (PGD)-algoritme niet alleen als een solver, maar als een discreet-tijds dynamisch systeem:
$$\xi_{k+1} = \text{proj}_{S_C}(\xi_k - \alpha_k \nabla_\xi J(\xi_k, \theta))$$

• Kerninzicht: Voor een vaste parameter $\theta$ convergeert PGD exponentieel naar het unieke minimum $\xi^\star(\theta)$.
• Onzekerheidsmodellering: De parameter $\theta$ wordt behandeld als een constante maar onbekende beginstaat. De verzameling van alle mogelijke PGD-trajecten die starten vanuit een vast beginpunt $\xi_0$ maar variëren over $\theta \in \Theta$, vormt een voorwaartse bereikbare verzameling.
• Convergentiegarantie: De auteurs bewijzen dat de afstand tussen de PGD-iteraties op stap $k$ en de ware verzameling van minima exponentieel afneemt met snelheid $\gamma^k$. Derhalve biedt de bereikbare verzameling op stap $k$, opgeblazen met deze exponentiële foutgrens, een gecertificeerde buitenbenadering van de verzameling van minima.

B. System-Level Synthesis (SLS) voor Bereikbaarheid

Om deze bereikbare verzamelingen efficiënt te berekenen (vooral voor hoog-dimensionale systemen), maken de auteurs gebruik van System-Level Synthesis (SLS):

1. Nominale Trajectorie & Foutdynamica: Zij definiëren een nominale trajectorie $(\hat{\xi}, \hat{\theta})$ en analyseren de foutdynamica ($\Delta \xi, \Delta \theta$) tussen het ware systeem en het nominale systeem.
2. Lineair Tijdsvariërend (LTV) Benadering: De niet-lineaire PGD-dynamica worden lineariseerd rond de nominale trajectorie. De foutpropagatie wordt gemodelleerd als een LTV-systeem dat wordt aangedreven door verstoringen (linearisatiefouten).
3. Feedbackontwerp: In plaats van vaste stapgroottes ontwerpen zij een causale affiene output-feedbackwet (met gebruik van SLS) om de reeks stapgroottes $\alpha_k$ te optimaliseren. Deze feedback minimaliseert de propagatie van onzekerheid, wat resulteert in strakkere grenzen voor de bereikbare verzameling in vergelijking met vaste-stap benaderingen.
4. Optimalisatie: Zij formuleren een Niet-Lineair Program (NLP) om de systeemrespons-matrices te vinden die de grootte van de uiteindelijke bereikbare verzameling minimaliseren, terwijl tegelijkertijd de robuuste voldoening aan stapgrootte-beperkingen wordt gewaarborgd.

C. Omgaan met Niet-Differentieerbaarheid

Voor beperkte problemen waarbij de projectie-operator $\text{proj}_{S_C}$ niet-differentieerbaar is (bijvoorbeeld niet-affiene beperkingsverzamelingen):

• Vervaging: Zij passen een op steekproeven gebaseerde vervagingsmethode toe. De niet-gladde PGD-update wordt benaderd door een vervagde versie $\tilde{f}$ via convolutie met een uniforme verdeling.
• Foutgrenzen: De methode houdt rekening met zowel de linearisatiefout van de vervagde dynamica als de benaderingsfout tussen de ware en vervagde dynamica, zodat de uiteindelijke grenzen geldig en gecertificeerd blijven.

3. Belangrijkste Bijdragen

1. Theoretische Herformulering: Bewezen dat het over-benaderen van de verzameling van minima equivalent is aan het berekenen van de voorwaartse bereikbare verzamelingen van PGD-dynamica met een onbekende parameter, waarbij gebruik wordt gemaakt van de exponentiële convergentie van PGD om expliciete foutgrenzen te bieden.
2. Op SLS Gebaseerde Bereikbaarheid: Ontwikkelde een hanteerbaar kader met behulp van SLS om voorwaartse bereikbare verzamelingen te berekenen voor hoog-dimensionale, gladde PGD-dynamica met lage conservativiteit.
3. Extensie voor Niet-Gladde Systemen: Breidde het kader uit tot niet-differentieerbare PGD-dynamica (vaak voorkomend in beperkte optimalisatie) via een vervagingsmethode, waarbij rigoureuze grenzen voor de benaderingsfout werden afgeleid.
4. Optimalisatie van Stapgroottes: Aangetoond dat het optimaliseren van de reeks stapgroottes via SLS aanzienlijk strakkere grenzen oplevert dan vaste-stap baselines of traditionele gevoeligheidsanalyse.

4. Resultaten en Simulaties

De auteurs hebben hun methode gevalideerd op drie scenario's:

1. Scalaire Quadratische Optimalisatie: Een eenvoudig onbeperkt probleem waarbij de ware verzameling van minima analytisch bekend is. De op SLS gebaseerde grenzen waren strak en bevatten de ware verzameling correct.
2. Hoog-dimensionale LQR met Intentie-Onzekerheid: Een 64-dimensionaal Lineair Quadratisch Regulator-probleem.
   • Vergelijking: Vergelijken met klassieke methoden op basis van de Implicit Function Theorem (gevoeligheidsanalyse).
   • Prestatie: De SLS-methode produceerde grenzen met een maximale breedte van 0,2, terwijl de gevoeligheidsanalyse-baseline een grensbreedte van ~35 produceerde. Dit onderstreept een enorme reductie in conservativiteit.
3. Beperkte Quadratische Optimalisatie: Een probleem met niet-affiene beperkingen (niet-gladde PGD).
   • De vervagingsmethode slaagde erin de niet-differentieerbaarheid te hanteren. Hoewel iets conservatiever dan het gladde geval vanwege de vervagingsfout, leverde de methode nog steeds geldige, gecertificeerde over-benaderingen op.

5. Betekenis

• Veiligheidskritieke Planning: Door strakke, gecertificeerde grenzen te bieden op de verzameling van mogelijke optimale beslissingen onder onzekerheid, maakt deze methode veiligere downstream planning mogelijk in robotica en autonome systemen. Het vermijdt het "pessimisme" van worst-case robuuste optimalisatie, terwijl het het "risico" van het negeren van onzekerheid voorkomt.
• Schaalbaarheid: Het gebruik van SLS stelt de methode in staat om op hanteerbare wijze te schalen naar hoog-dimensionale beslissingsruimten (gedemonstreerd tot 64 dimensies), een regime waar traditionele op verzamelingen gebaseerde bereikbaarheid of gevoeligheidsanalyse vaak faalt of te conservatief wordt.
• Nieuwe Intersectie: Het artikel slaagt erin convexe optimalisatietheorie (convergentie van PGD) te verbinden met besturingstheorie (bereikbaarheidsanalyse en SLS), en biedt zo een nieuw paradigma voor het analyseren van parametrische optimalisatieproblemen.

Kortom, dit werk biedt een wiskundig rigoureuze, computationeel efficiënte en laag-conservatieve aanpak om te begrijpen hoe onzekerheid in probleemparameters zich voortplant naar de verzameling van optimale oplossingen, een cruciale capaciteit voor robuuste autonome besluitvorming.