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

Résumé Technique : Approximation pilotée par les données des bassins d'attraction via une sélection de fonctions de Lyapunov PWA basée sur la programmation linéaire

Formulation du problème
L'article aborde le défi de la certification de la stabilité et de l'approximation du bassin d'attraction (RoA) pour des systèmes dynamiques non linéaires à champs vectoriels inconnus, $\dot{x} = f(x)$. L'analyse de stabilité traditionnelle repose sur des modèles mathématiques explicites, souvent indisponibles pour les systèmes non linéaires complexes. Bien que des méthodes pilotées par les données existent, beaucoup (telles que les approches basées sur les réseaux de neurones) manquent de garanties explicites de robustesse, tandis que d'autres (comme les sommes de carrés) reposent sur des hypothèses structurelles qui peuvent limiter leur applicabilité entièrement pilotée par les données.

L'objectif est de construire un RoA certifié en utilisant uniquement des évaluations ponctuelles du champ vectoriel (données) et des bornes de continuité de Lipschitz connues. Le problème suppose :

1. Un équilibre localement asymptotiquement stable unique (pris comme l'origine).
2. Le champ vectoriel $f$ est continu au sens de Lipschitz avec une borne supérieure connue composante par composante $M$.
3. Un ensemble de données $D_{N_d} = \{(x_i, f_i)\}$ est disponible provenant de simulations ou de mesures.
4. Un petit ensemble polyédrique sûr $A$ contenant l'équilibre existe.

Méthodologie
Le cadre proposé procède en trois étapes principales : caractérisation de l'incertitude, tessellation de l'espace d'état et synthèse de candidat de Lyapunov via la programmation linéaire (LP).

1. Construction de l'ensemble d'incertitude :
   Sur la base de l'hypothèse de continuité de Lipschitz et des données disponibles, les auteurs construisent un ensemble d'incertitude polyédrique $F_{D_{N_d}}$ représentant tous les champs vectoriels admissibles cohérents avec les données.

   • Pour chaque point de données $(x_i, f_i)$, la contrainte de Lipschitz $|f(x) - f_i| \leq M\|x - x_i\|_\infty$ définit un ensemble de valeurs admissibles.
   • Cette contrainte est reformulée en une union de cônes polyédriques dans $\mathbb{R}^{n+1}$ (état et valeur du champ vectoriel).
   • L'ensemble global d'incertitude est l'intersection de ces ensembles sur tous les points de données.
   • Crucialement, pour tout état $x$, l'ensemble des valeurs admissibles du champ vectoriel $F(x)$ forme un hyperrectangle (un produit cartésien d'intervalles). Cette application à valeurs ensembles permet de décrire la dynamique du système comme une inclusion différentielle $\dot{x} \in F(x)$.

2. Tessellation de l'espace d'état et candidat PWA :
   L'espace d'état $X$ est partitionné en une tessellation polyédrique $\{Y_j\}$. Les sommets de cette tessellation sont dérivés des projections des sommets du graphe de l'ensemble d'incertitude $F(x)$ sur l'espace d'état. Cela garantit que la partition s'aligne avec la structure géométrique de l'incertitude.
   Un candidat de Lyapunov continu par morceaux affines (PWA) $V(x)$ est défini sur cette partition :
   $$V(x) = a_j^T x + b_j, \quad \forall x \in Y_j$$
   Les coefficients $(a_j, b_j)$ sont les variables de décision à déterminer.

3. Synthèse basée sur la LP :
   Les auteurs formulent un programme linéaire (LP) pour sélectionner les coefficients $(a_j, b_j)$ tels que $V(x)$ satisfasse les conditions de Lyapunov pour toutes les dynamiques admissibles dans $F(x)$.

   • Positivité et continuité : Imposées via des contraintes linéaires aux sommets de la tessellation et le long des frontières des cellules.
   • Condition de décroissance : La condition $\nabla V(x)^T f(x) < 0$ doit être vérifiée pour tout $f(x) \in F(x)$. Puisque $F(x)$ est un hyperrectangle convexe, son maximum est atteint à ses sommets. Ainsi, la condition est imposée uniquement sur l'ensemble fini de sommets $F_v(x)$ de l'hyperrectangle.
   • Relaxation : Des variables d'écart sont introduites pour gérer l'infaisabilité (par exemple, près de l'équilibre ou là où les données sont insuffisantes), permettant un processus de raffinement itératif.

4. Algorithme itératif :
   Un algorithme itératif (Algorithme 1) est proposé :

   • Construire l'ensemble d'incertitude et extraire les sommets.
   • Résoudre le LP.
   • Si la condition de décroissance de Lyapunov n'est pas satisfaite (indiquée par des variables d'écart non négatives) ou si l'ensemble d'incertitude contient zéro (indiquant des données insuffisantes), de nouveaux points de données sont ajoutés aux sommets problématiques.
   • Le processus se répète jusqu'à ce qu'un RoA valide soit certifié ou que les limites d'itération soient atteintes.

Contributions clés

• Modélisation explicite de l'incertitude : L'article fournit une méthode rigoureuse pour construire un ensemble d'incertitude polyédrique à partir de données éparses et de bornes de Lipschitz, convertissant les dynamiques inconnues en une inclusion différentielle traitable.
• Certification basée sur la LP : Contrairement aux méthodes alternatives qui reposent sur la programmation en cônes du second ordre (SOCP) ou les réseaux de neurones, cette approche formule la certification de stabilité comme un programme linéaire. Cela est réalisé en exploitant la structure d'hyperrectangle de l'ensemble d'incertitude et en évaluant les conditions uniquement à ses sommets.
• Séparation des préoccupations : La méthodologie découple la caractérisation de l'incertitude de la synthèse de Lyapunov. Cette approche en deux étapes améliore l'interprétabilité et permet un raffinement itératif basé sur l'informativité des données.
• Extraction de RoA certifié : La méthode garantit que l'ensemble de sous-niveau de la fonction PWA résultante, restreint à la composante connexe contenant l'équilibre, est un bassin d'attraction valide cohérent avec les données.

Résultats numériques
La méthode a été validée sur deux exemples : un pendule amorti simple et un oscillateur de Van der Pol inversé dans le temps.

• Pendule amorti : L'algorithme a convergé en 4 itérations, extrayant avec succès un RoA certifié correspondant à la forme du vrai RoA. Le temps d'optimisation était négligeable par rapport au temps de traitement des données requis pour calculer les bornes d'incertitude.
• Oscillateur de Van der Pol : La méthode a convergé en 3 itérations. Bien que le RoA certifié ait été identifié avec succès, les résultats ont mis en évidence que la condition de décroissance de Lyapunov n'était pas satisfaite globalement (certaines variables d'écart sont restées non négatives en dehors de la région certifiée), démontrant la capacité de la méthode à fournir des bornes conservatrices et certifiées même lorsque la stabilité globale ne peut être prouvée à partir des données disponibles.

Signification et revendications
L'article revendique que sa contribution principale est un cadre entièrement piloté par les données et traitable pour la certification de stabilité qui évite la nature de "boîte noire" des réseaux de neurones et les hypothèses structurelles des méthodes polynomiales. En combinant des ensembles d'incertitude explicites avec des fonctions de Lyapunov PWA, l'approche offre :

1. Robustesse : Les garanties s'appliquent à toutes les dynamiques cohérentes avec les données et les bornes de Lipschitz, et pas seulement aux points échantillonnés.
2. Traitabilité computationnelle : L'utilisation de la LP rend le problème évolutif par rapport aux formulations SOCP.
3. Interprétabilité : La séparation de la modélisation de l'incertitude et de la sélection de Lyapunov fournit un processus de certification clair et étape par étape.

Les auteurs positionnent ce travail comme un pont entre la théorie du contrôle robuste (inclusions différentielles) et le contrôle moderne piloté par les données, offrant un outil pratique pour extraire des propriétés de stabilité certifiées à partir de données éparses sans nécessiter de modèle paramétrique du système.