Abstract
Discrete-Time Linear Complementarity Systems (DLCS) represent a critical class of hybrid dynamical systems used to model physical phenomena involving intermittent contact, such as robotics and power electronics. While continuous-time theory is mature, verifying stability in discrete-time implementations remains a significant challenge. This paper presents the first exact algorithm for the stability verification of DLCS. By utilizing a novel cutting-plane approach and Extended Quadratic Lyapunov Functions (EQLF), the researchers provide a non-conservative method to guarantee system safety.
Introduction
In modern engineering, many systems exhibit "switching" behaviors where the governing physics change abruptly. A classic example is a robotic manipulator: its dynamics transition instantly when it makes contact with a surface. These systems are often modeled as Linear Complementarity Systems (LCS), where algebraic variables solve a Linear Complementarity Problem (LCP) to determine the current mode of operation.
While physical systems exist in continuous time, control systems are implemented on digital hardware operating in discrete steps. This necessitates the study of Discrete-Time Linear Complementarity Systems (DLCS). Historically, analyzing the stability of DLCS—ensuring the system returns to equilibrium after a disturbance—has been difficult. Existing methods often relied on "conservative" approximations that might fail to prove stability even when a system is inherently stable.
Lyapunov Stability in DLCS
The researchers focus on finding Lyapunov functions, which act as mathematical "energy" metrics that must strictly decrease over time for a system to be considered stable. The paper explores two primary formulations:
- Common Quadratic Lyapunov Function (CQLF): A standard quadratic form that depends solely on the state vector.
- Extended Quadratic Lyapunov Function (EQLF): A more flexible function that incorporates both the state variables and the algebraic variables from the LCP.
The inclusion of EQLFs is a significant advancement. The study demonstrates that EQLFs can prove stability in complex scenarios where CQLFs fail, particularly in systems with intricate switching logic (such as the cam33 benchmark).
The Cutting-Plane Algorithm
Verifying the stability of these systems is computationally demanding, categorized as a co-NP-complete problem. The authors frame the search for a Lyapunov function as a copositive program over nonconvex cones. To solve this, they propose a novel, exact cutting-plane algorithm.
The algorithm functions through an iterative process between two components:
- The Master Problem: A linear program that searches for a candidate Lyapunov function.
- The Separation Problem: Formulated as a Mixed Integer Quadratically Constrained Program (MIQCP), this step searches for "counter-examples"—specific states where the candidate function fails to decrease.
If the Separation Problem identifies a counter-example, it is added as a new constraint to the Master Problem, "cutting" away the invalid region of the search space. This process repeats until a valid Lyapunov function is found or the system is proven unstable.
Key Theoretical and Numerical Insights
A major contribution of this work is the theoretical bridge between continuous and discrete domains. The authors prove that if a continuous-time LCS is stable, its DLCS counterpart is also stable for sufficiently small time steps. This provides a rigorous justification for the common engineering practice of discretizing continuous models.
Furthermore, the research highlights the impact of discretization methods. Systems discretized using the Implicit Euler method were found to be generally easier to stabilize and verify than those using the Explicit Euler method, aligning with long-standing intuitions in numerical analysis regarding the stability of implicit schemes.
Experimental Results
The algorithm was implemented in Python using the Gurobi optimizer and tested against several benchmark models, including the cam31-33 and hem2 systems.
- Exactness: Unlike previous relaxation methods (such as those using the S-Lemma), this approach is exact. If a quadratic Lyapunov function exists, the algorithm is guaranteed to find it.
- Efficiency: For systems with up to four states, the algorithm typically converged within 1 to 35 iterations, often requiring less than one second of CPU time.
- Validation: The researchers validated the results by running 100 random simulations for each system, confirming that the computed Lyapunov functions decreased along every trajectory.
Conclusion and Future Work
This research provides a robust framework for the safety verification of hybrid systems. While highly effective for small-to-medium benchmarks, future work will focus on scaling the cutting-plane approach for high-dimensional robotics models. Additionally, the authors aim to extend this analysis to systems with active feedback control, which introduces "bilinear" complexities into the optimization problems.
Summary updated