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

Technical Summary: Data-driven Approximation of Regions of Attraction via LP-based Selection of PWA Lyapunov Functions

Problem Formulation
The paper addresses the challenge of certifying the stability and approximating the Region of Attraction (RoA) for nonlinear dynamical systems with unknown vector fields, $\dot{x} = f(x)$. Traditional stability analysis relies on explicit mathematical models, which are often unavailable for complex nonlinear systems. While data-driven methods exist, many (such as neural network-based approaches) lack explicit robustness guarantees, and others (like Sum-of-Squares) rely on structural assumptions that may limit fully data-driven applicability.

The objective is to construct a certified RoA using only point-wise evaluations of the vector field (data) and known Lipschitz continuity bounds. The problem assumes:

1. A unique locally asymptotically stable equilibrium (taken as the origin).
2. The vector field $f$ is Lipschitz continuous with a known component-wise upper bound $M$.
3. A dataset $D_{N_d} = \{(x_i, f_i)\}$ is available from simulations or measurements.
4. A small safe polyhedral set $A$ containing the equilibrium exists.

Methodology
The proposed framework proceeds in three main stages: uncertainty characterization, state-space tessellation, and Lyapunov candidate synthesis via Linear Programming (LP).

1. Uncertainty Set Construction:
   Based on the Lipschitz continuity assumption and the available data, the authors construct a polyhedral uncertainty set $F_{D_{N_d}}$ representing all admissible vector fields consistent with the data.

   • For each data point $(x_i, f_i)$, the Lipschitz constraint $|f(x) - f_i| \leq M\|x - x_i\|_\infty$ defines a set of admissible values.
   • This constraint is reformulated into a union of polyhedral cones in $\mathbb{R}^{n+1}$ (state and vector field value).
   • The global uncertainty set is the intersection of these sets over all data points.
   • Crucially, for any state $x$, the set of admissible vector field values $F(x)$ forms a hyperbox (a Cartesian product of intervals). This set-valued map allows the system dynamics to be described as a differential inclusion $\dot{x} \in F(x)$.

2. State-Space Tessellation and PWA Candidate:
   The state space $X$ is partitioned into a polyhedral tessellation $\{Y_j\}$. The vertices of this tessellation are derived from the projections of the vertices of the graph of the uncertainty set $F(x)$ onto the state space. This ensures the partition aligns with the geometric structure of the uncertainty.
   A Continuous Piecewise Affine (PWA) Lyapunov candidate $V(x)$ is defined over this partition:
   $$V(x) = a_j^T x + b_j, \quad \forall x \in Y_j$$
   The coefficients $(a_j, b_j)$ are the decision variables to be determined.

3. LP-based Synthesis:
   The authors formulate a Linear Program (LP) to select the coefficients $(a_j, b_j)$ such that $V(x)$ satisfies Lyapunov conditions for all admissible dynamics in $F(x)$.

   • Positivity and Continuity: Enforced via linear constraints at the tessellation vertices and along cell boundaries.
   • Decrease Condition: The condition $\nabla V(x)^T f(x) < 0$ must hold for all $f(x) \in F(x)$. Since $F(x)$ is a convex hyperbox, its maximum is attained at its vertices. Thus, the condition is enforced only at the finite set of vertices $F_v(x)$ of the hyperbox.
   • Relaxation: Slack variables are introduced to handle infeasibility (e.g., near the equilibrium or where data is insufficient), allowing an iterative refinement process.

4. Iterative Algorithm:
   An iterative algorithm (Algorithm 1) is proposed:

   • Construct the uncertainty set and extract vertices.
   • Solve the LP.
   • If the Lyapunov decrease condition is not satisfied (indicated by non-negative slack variables) or if the uncertainty set contains zero (indicating insufficient data), new data points are added at the problematic vertices.
   • The process repeats until a valid RoA is certified or iteration limits are reached.

Key Contributions

• Explicit Uncertainty Modeling: The paper provides a rigorous method to construct a polyhedral uncertainty set from sparse data and Lipschitz bounds, converting the unknown dynamics into a tractable differential inclusion.
• LP-based Certification: Unlike alternative methods that rely on Second-Order Cone Programming (SOCP) or neural networks, this approach formulates the stability certification as a Linear Program. This is achieved by exploiting the hyperbox structure of the uncertainty set and evaluating conditions only at its vertices.
• Separation of Concerns: The methodology decouples the characterization of uncertainty from the Lyapunov synthesis. This two-stage approach improves interpretability and allows for iterative refinement based on data informativity.
• Certified RoA Extraction: The method guarantees that the sublevel set of the resulting PWA function, restricted to the connected component containing the equilibrium, is a valid Region of Attraction consistent with the data.

Numerical Results
The method was validated on two examples: a simple damped pendulum and an inverted-time Van der Pol oscillator.

• Damped Pendulum: The algorithm converged in 4 iterations, successfully extracting a certified RoA that matched the shape of the true RoA. The optimization time was negligible compared to the data processing time required to compute uncertainty bounds.
• Van der Pol Oscillator: The method converged in 3 iterations. While the certified RoA was successfully identified, the results highlighted that the Lyapunov decrease condition was not satisfied globally (some slack variables remained non-negative outside the certified region), demonstrating the method's ability to provide conservative, certified bounds even when global stability cannot be proven from the available data.

Significance and Claims
The paper claims that its primary contribution is a tractable, fully data-driven framework for stability certification that avoids the "black box" nature of neural networks and the structural assumptions of polynomial methods. By combining explicit uncertainty sets with PWA Lyapunov functions, the approach offers:

1. Robustness: Guarantees hold for all dynamics consistent with the data and Lipschitz bounds, not just the sampled points.
2. Computational Tractability: The use of LP makes the problem scalable compared to SOCP formulations.
3. Interpretability: The separation of uncertainty modeling and Lyapunov selection provides a clear, step-by-step certification process.

The authors position this work as a bridge between theoretical robust control (differential inclusions) and modern data-driven control, offering a practical tool for extracting certified stability properties from sparse data without requiring a parametric model of the system.