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

Technische Zusammenfassung: Datengetriebene Approximation von Einzugsgebieten durch LP-basierte Auswahl von PWA-Lyapunov-Funktionen

Problemformulierung
Der Beitrag adressiert die Herausforderung, die Stabilität nichtlinearer dynamischer Systeme mit unbekannten Vektorfeldern, $\dot{x} = f(x)$, zu zertifizieren und das Einzugsgebiet (Region of Attraction, RoA) zu approximieren. Die traditionelle Stabilitätsanalyse stützt sich auf explizite mathematische Modelle, die für komplexe nichtlineare Systeme oft nicht verfügbar sind. Zwar existieren datengetriebene Methoden, doch viele (wie neuronale Netz-basierte Ansätze) bieten keine expliziten Robustheitsgarantien, und andere (wie Sum-of-Squares) beruhen auf strukturellen Annahmen, die eine vollständig datengetriebene Anwendbarkeit einschränken können.

Das Ziel besteht darin, ein zertifiziertes RoA ausschließlich unter Verwendung von punktweisen Auswertungen des Vektorfelds (Daten) und bekannten Lipschitz-Stetigkeitsgrenzen zu konstruieren. Das Problem geht von folgenden Voraussetzungen aus:

1. Ein eindeutiges lokal asymptotisch stabiles Gleichgewicht (als Ursprung angenommen).
2. Das Vektorfeld $f$ ist Lipschitz-stetig mit einer bekannten komponentenweisen oberen Schranke $M$.
3. Ein Datensatz $D_{N_d} = \{(x_i, f_i)\}$ ist aus Simulationen oder Messungen verfügbar.
4. Eine kleine sichere polyedrische Menge $A$, die das Gleichgewicht enthält, existiert.

Methodik
Der vorgeschlagene Rahmenwerk durchläuft drei Hauptphasen: Charakterisierung der Unsicherheit, Zerlegung des Zustandsraums und Synthese von Lyapunov-Kandidaten mittels Linearer Programmierung (LP).

1. Konstruktion der Unsicherheitsmenge:
   Basierend auf der Annahme der Lipschitz-Stetigkeit und den verfügbaren Daten konstruieren die Autoren eine polyedrische Unsicherheitsmenge $F_{D_{N_d}}$, die alle zulässigen Vektorfelder darstellt, die mit den Daten konsistent sind.

   • Für jeden Datenpunkt $(x_i, f_i)$ definiert die Lipschitz-Bedingung $|f(x) - f_i| \leq M\|x - x_i\|_\infty$ eine Menge zulässiger Werte.
   • Diese Bedingung wird in eine Vereinigung polyedrischer Kegel im $\mathbb{R}^{n+1}$ (Zustand und Vektorfeldwert) umformuliert.
   • Die globale Unsicherheitsmenge ist der Schnitt dieser Mengen über alle Datenpunkte.
   • Entscheidend ist, dass für jeden Zustand $x$ die Menge der zulässigen Vektorfeldwerte $F(x)$ einen Hyperquader (ein kartesisches Produkt von Intervallen) bildet. Diese mengenwertige Abbildung ermöglicht es, die Systemdynamik als Differentialinklusion $\dot{x} \in F(x)$ zu beschreiben.

2. Zustandsraum-Zerlegung und PWA-Kandidat:
   Der Zustandsraum $X$ wird in eine polyedrische Zerlegung (Tessellation) $\{Y_j\}$ unterteilt. Die Eckpunkte dieser Zerlegung werden aus den Projektionen der Eckpunkte des Graphen der Unsicherheitsmenge $F(x)$ auf den Zustandsraum abgeleitet. Dies stellt sicher, dass die Partition mit der geometrischen Struktur der Unsicherheit übereinstimmt.
   Über diese Partition wird ein stetiges, stückweise affines (PWA) Lyapunov-Kandidat $V(x)$ definiert:
   $$V(x) = a_j^T x + b_j, \quad \forall x \in Y_j$$
   Die Koeffizienten $(a_j, b_j)$ sind die zu bestimmenden Entscheidungsvariablen.

3. LP-basierte Synthese:
   Die Autoren formulieren ein Lineares Programm (LP), um die Koeffizienten $(a_j, b_j)$ so zu wählen, dass $V(x)$ die Lyapunov-Bedingungen für alle zulässigen Dynamiken in $F(x)$ erfüllt.

   • Positivität und Stetigkeit: Werden durch lineare Nebenbedingungen an den Eckpunkten der Zerlegung und entlang der Zellgrenzen erzwungen.
   • Abnahme-Bedingung: Die Bedingung $\nabla V(x)^T f(x) < 0$ muss für alle $f(x) \in F(x)$ gelten. Da $F(x)$ ein konvexer Hyperquader ist, wird sein Maximum an seinen Eckpunkten angenommen. Daher wird die Bedingung nur an der endlichen Menge der Eckpunkte $F_v(x)$ des Hyperquaders erzwungen.
   • Relaxierung: Schlupfvariablen werden eingeführt, um Unzulässigkeiten zu handhaben (z. B. in der Nähe des Gleichgewichts oder wo Daten unzureichend sind), was einen iterativen Verfeinerungsprozess ermöglicht.

4. Iterativer Algorithmus:
   Ein iterativer Algorithmus (Algorithmus 1) wird vorgeschlagen:

   • Konstruktion der Unsicherheitsmenge und Extraktion der Eckpunkte.
   • Lösung des LP.
   • Wenn die Lyapunov-Abnahme-Bedingung nicht erfüllt ist (angezeigt durch nicht-negative Schlupfvariablen) oder wenn die Unsicherheitsmenge Null enthält (was auf unzureichende Daten hinweist), werden neue Datenpunkte an den problematischen Eckpunkten hinzugefügt.
   • Der Prozess wiederholt sich, bis ein gültiges RoA zertifiziert ist oder Iterationsgrenzen erreicht werden.

Hauptbeiträge

• Explizite Unsicherheitsmodellierung: Der Beitrag liefert eine rigorose Methode zur Konstruktion einer polyedrischen Unsicherheitsmenge aus spärlichen Daten und Lipschitz-Grenzen, wodurch die unbekannte Dynamik in eine handhabbare Differentialinklusion überführt wird.
• LP-basierte Zertifizierung: Im Gegensatz zu alternativen Methoden, die auf Second-Order-Cone-Programmierung (SOCP) oder neuronalen Netzen beruhen, formuliert dieser Ansatz die Stabilitätszertifizierung als Lineares Programm. Dies wird durch Ausnutzung der Hyperquader-Struktur der Unsicherheitsmenge und der Evaluierung der Bedingungen ausschließlich an deren Eckpunkten erreicht.
• Trennung der Anliegen: Die Methodik entkoppelt die Charakterisierung der Unsicherheit von der Lyapunov-Synthese. Dieser zweistufige Ansatz verbessert die Interpretierbarkeit und ermöglicht eine iterative Verfeinerung basierend auf der Informationsgehalt der Daten.
• Zertifizierte RoA-Extraktion: Die Methode garantiert, dass die Subniveaumenge der resultierenden PWA-Funktion, eingeschränkt auf die zusammenhängende Komponente, die das Gleichgewicht enthält, ein gültiges Einzugsgebiet ist, das mit den Daten konsistent ist.

Numerische Ergebnisse
Die Methode wurde an zwei Beispielen validiert: einem einfachen gedämpften Pendel und einem invertierten Van-der-Pol-Oszillator.

• Gedämpftes Pendel: Der Algorithmus konvergierte in 4 Iterationen und extrahierte erfolgreich ein zertifiziertes RoA, das der Form des wahren RoA entsprach. Die Optimierungszeit war vernachlässigbar im Vergleich zur für die Berechnung der Unsicherheitsgrenzen erforderlichen Datenverarbeitungszeit.
• Van-der-Pol-Oszillator: Die Methode konvergierte in 3 Iterationen. Obwohl das zertifizierte RoA erfolgreich identifiziert wurde, zeigten die Ergebnisse, dass die Lyapunov-Abnahme-Bedingung nicht global erfüllt war (einige Schlupfvariablen blieben außerhalb des zertifizierten Bereichs nicht-negativ). Dies demonstriert die Fähigkeit der Methode, konservative, zertifizierte Grenzen bereitzustellen, selbst wenn eine globale Stabilität aus den verfügbaren Daten nicht bewiesen werden kann.

Bedeutung und Behauptungen
Der Beitrag behauptet, dass sein primärer Beitrag ein handhabbarer, vollständig datengetriebener Rahmen für die Stabilitätszertifizierung ist, der die „Black-Box"-Natur neuronaler Netze und die strukturellen Annahmen polynomialer Methoden vermeidet. Durch die Kombination expliziter Unsicherheitsmengen mit PWA-Lyapunov-Funktionen bietet der Ansatz:

1. Robustheit: Die Garantien gelten für alle Dynamiken, die mit den Daten und den Lipschitz-Grenzen konsistent sind, nicht nur für die gesampelten Punkte.
2. Rechenbarkeit: Die Verwendung von LP macht das Problem im Vergleich zu SOCP-Formulierungen skalierbar.
3. Interpretierbarkeit: Die Trennung von Unsicherheitsmodellierung und Lyapunov-Auswahl bietet einen klaren, schrittweisen Zertifizierungsprozess.

Die Autoren positionieren diese Arbeit als Brücke zwischen theoretischer robuster Regelung (Differentialinklusionen) und moderner datengetriebener Regelung und bieten ein praktisches Werkzeug zur Extraktion zertifizierter Stabilitätseigenschaften aus spärlichen Daten, ohne ein parametrisches Modell des Systems zu benötigen.