Data-driven approximation of regions of attraction via an LP-based selection of PWA Lyapunov functions

Technische Samenvatting: Datagedreven Benadering van Aantrekkingsgebieden via LP-gebaseerde Selectie van PWA-Lyapunovfuncties

Probleemformulering
Het artikel adresseert de uitdaging om stabiliteit te certificeren en het Aantrekkingsgebied (RoA) te benaderen voor niet-lineaire dynamische systemen met onbekende vectorvelden, $\dot{x} = f(x)$. Traditionele stabiliteitsanalyse vertrouwt op expliciete wiskundige modellen, die vaak niet beschikbaar zijn voor complexe niet-lineaire systemen. Hoewel datagedreven methoden bestaan, missen velen (zoals op neurale netwerken gebaseerde benaderingen) expliciete robuustheidsgaranties, en andere (zoals Som-van-Kwadraten) vertrouwen op structurele aannames die de volledig datagedreven toepasbaarheid kunnen beperken.

Het doel is om een gecertificeerd RoA te construeren uitsluitend met behulp van puntsgewijze evaluaties van het vectorveld (data) en bekende Lipschitz-continuïteitsgrenzen. Het probleem gaat uit van:

1. Een uniek lokaal asymptotisch stabiel evenwicht (genomen als de oorsprong).
2. Het vectorveld $f$ is Lipschitz-continu met een bekende componentsgewijze bovengrens $M$.
3. Een dataset $D_{N_d} = \{(x_i, f_i)\}$ is beschikbaar uit simulaties of metingen.
4. Een klein veilig polyedrisch gebied $A$ dat het evenwicht bevat, bestaat.

Methodologie
Het voorgestelde kader verloopt in drie hoofdfasen: karakterisering van onzekerheid, tesselatie van de toestandsruimte, en synthese van Lyapunov-kandidaten via Lineaire Programmering (LP).

1. Constructie van het Onzekerheidsset:
   Op basis van de aanname van Lipschitz-continuïteit en de beschikbare data construeren de auteurs een polyedrisch onzekerheidsset $F_{N_d}$ dat alle toelaatbare vectorvelden vertegenwoordigt die consistent zijn met de data.

   • Voor elk datapunt $(x_i, f_i)$ definieert de Lipschitz-beperking $|f(x) - f_i| \leq M\|x - x_i\|_\infty$ een set van toelaatbare waarden.
   • Deze beperking wordt herformuleerd tot een unie van polyedrische kegels in $\mathbb{R}^{n+1}$ (toestand en vectorveldwaarde).
   • Het globale onzekerheidsset is de doorsnede van deze sets over alle datapunten.
   • Cruciaal is dat, voor elke toestand $x$, de set van toelaatbare vectorveldwaarden $F(x)$ een hyperdoos vormt (een Cartesisch product van intervallen). Deze verzamelingwaarde-afbeelding staat toe dat de systeemdynamica wordt beschreven als een differentiaalopsluiting $\dot{x} \in F(x)$.

2. Tesselatie van de Toestandsruimte en PWA-kandidaat:
   De toestandsruimte $X$ wordt gepartitioneerd in een polyedrische tesselatie $\{Y_j\}$. De hoekpunten van deze tesselatie zijn afgeleid van de projecties van de hoekpunten van de grafiek van het onzekerheidsset $F(x)$ op de toestandsruimte. Dit zorgt ervoor dat de partitionering aligneert met de geometrische structuur van de onzekerheid.
   Een Continue Stuksgewijs Affiene (PWA) Lyapunov-kandidaat $V(x)$ wordt gedefinieerd over deze partitionering:
   $$V(x) = a_j^T x + b_j, \quad \forall x \in Y_j$$
   De coëfficiënten $(a_j, b_j)$ zijn de beslisvariabelen die moeten worden bepaald.

3. LP-gebaseerde Synthese:
   De auteurs formuleren een Lineair Program (LP) om de coëfficiënten $(a_j, b_j)$ te selecteren zodat $V(x)$ voldoet aan Lyapunov-condities voor alle toelaatbare dynamica in $F(x)$.

   • Positiviteit en Continuïteit: Afgedwongen via lineaire beperkingen op de hoekpunten van de tesselatie en langs celgrenzen.
   • Afnameconditie: De conditie $\nabla V(x)^T f(x) < 0$ moet gelden voor alle $f(x) \in F(x)$. Aangezien $F(x)$ een convexe hyperdoos is, wordt het maximum bereikt op de hoekpunten. Derhalve wordt de conditie alleen afgedwongen op de eindige set van hoekpunten $F_v(x)$ van de hyperdoos.
   • Relaxatie: Slakvariabelen worden geïntroduceerd om onhaalbaarheid te behandelen (bijvoorbeeld nabij het evenwicht of waar data ontoereikend is), waardoor een iteratief verfijningsproces mogelijk wordt.

4. Iteratief Algorithm:
   Een iteratief algoritme (Algoritme 1) wordt voorgesteld:

   • Construeer het onzekerheidsset en extraher de hoekpunten.
   • Los het LP op.
   • Als de Lyapunov-afnameconditie niet wordt voldaan (aangegeven door niet-negatieve slakvariabelen) of als het onzekerheidsset nul bevat (wat wijst op ontoereikende data), worden nieuwe datapunten toegevoegd op de problematische hoekpunten.
   • Het proces herhaalt zich totdat een geldig RoA is gecertificeerd of iteratielimieten zijn bereikt.

Belangrijkste Bijdragen

• Expliciete Onzekerheidsmodellering: Het artikel biedt een rigoureuze methode om een polyedrisch onzekerheidsset te construeren uit schaarse data en Lipschitz-grenzen, waardoor de onbekende dynamica wordt omgezet in een hanteerbare differentiaalopsluiting.
• LP-gebaseerde Certificatie: In tegenstelling tot alternatieve methoden die vertrouwen op Second-Order Cone Programming (SOCP) of neurale netwerken, formuleert deze aanpak de stabiliteitscertificatie als een Lineair Program. Dit wordt bereikt door gebruik te maken van de hyperdoosstructuur van het onzekerheidsset en condities uitsluitend op de hoekpunten daarvan te evalueren.
• Scheiding van Belangen: De methodologie ontkoppelt de karakterisering van onzekerheid van de Lyapunov-synthese. Deze tweefasige aanpak verbetert de interpreteerbaarheid en staat iteratieve verfijning toe op basis van de informativiteit van de data.
• Gecertificeerde RoA-extractie: De methode garandeert dat de subniveaustel van de resulterende PWA-functie, beperkt tot de samenhangende component die het evenwicht bevat, een geldig Aantrekkingsgebied is dat consistent is met de data.

Numerieke Resultaten
De methode werd gevalideerd op twee voorbeelden: een eenvoudige gedempte slinger en een omgekeerde tijd Van der Pol-oscillator.

• Gedempte Slinger: Het algoritme convergeerde in 4 iteraties, waarbij succesvol een gecertificeerd RoA werd geëxtraheerd dat de vorm van het ware RoA matchte. De optimalisatietijd was verwaarloosbaar in vergelijking met de dataverwerkingstijd die nodig was om onzekerheidsgrenzen te berekenen.
• Van der Pol-oscillator: De methode convergeerde in 3 iteraties. Hoewel het gecertificeerde RoA succesvol werd geïdentificeerd, benadrukten de resultaten dat de Lyapunov-afnameconditie niet globaal werd voldaan (sommige slakvariabelen bleven niet-negatief buiten het gecertificeerde gebied), wat de capaciteit van de methode demonstreert om conservatieve, gecertificeerde grenzen te bieden, zelfs wanneer globale stabiliteit niet kan worden bewezen vanuit de beschikbare data.

Betekenis en Beweringen
Het artikel beweert dat de primaire bijdrage een hanteerbaar, volledig datagedreven kader is voor stabiliteitscertificatie dat de "black box"-aard van neurale netwerken en de structurele aannames van polynomiale methoden vermijdt. Door expliciete onzekerheidssets te combineren met PWA-Lyapunovfuncties, biedt de aanpak:

1. Robuustheid: Garanties gelden voor alle dynamica die consistent is met de data en Lipschitz-grenzen, niet alleen voor de bemonsterde punten.
2. Berekenbare Hanteerbaarheid: Het gebruik van LP maakt het probleem schaalbaar in vergelijking met SOCP-formuleringen.
3. Interpreteerbaarheid: De scheiding van onzekerheidsmodellering en Lyapunov-selectie biedt een duidelijk, stap-voor-stap certificeringsproces.

De auteurs positioneren dit werk als een brug tussen theoretische robuuste regeling (differentiaalopsluitingen) en moderne datagedreven regeling, en bieden een praktisch hulpmiddel voor het extraheren van gecertificeerde stabiliteitseigenschappen uit schaarse data zonder een parametrisch model van het systeem te vereisen.