TL;DR
This paper presents a novel algorithm for synthesizing Lyapunov functions for polynomial systems. It tackles the common issue of infeasible linear programs during synthesis by intelligently subdividing the problem domain, leading to faster convergence and more efficient solutions.
What Problem Does This Paper Address?
Proving the stability of dynamical systems is a cornerstone of control theory, and Lyapunov functions are a powerful tool for this. However, finding these functions, especially for complex nonlinear systems, is notoriously difficult. While methods like sum-of-squares programming have made significant strides, they often face the "curse of dimensionality," becoming computationally intractable for higher-dimensional systems. Existing approaches to overcome this, such as restricting the class of polynomials or using fixed subdivision strategies, have their own limitations. This paper addresses the challenge of efficiently synthesizing continuous piecewise-polynomial Lyapunov functions by developing an adaptive subdivision strategy that leverages information from infeasible linear programming problems.
Methods
The core of this work builds upon existing methods for Lyapunov function synthesis using Bernstein basis polynomials on simplices. The key innovation lies in how the algorithm handles infeasibility.
- Lyapunov Synthesis via Linear Programming (LP): The problem of finding a Lyapunov function is reformulated as a linear program. This involves expressing the system's vector field and the candidate Lyapunov function in the simplicial Bernstein basis. The conditions for a Lyapunov function (positivity and a negative Lie derivative) translate into linear constraints on the coefficients of these polynomials.
- Regular Subdivision: When the initial LP is infeasible (meaning no Lyapunov function of the specified degree and domain can be found), the algorithm resorts to subdividing the simplices in the domain. This increases the number of simplices and thus the number of variables in the LP, but aims to eventually make the problem solvable. The paper proves the convergence of this "regular subdivision" approach.
- Infeasibility Investigation (CII Method): The main contribution is an "irregular" subdivision strategy. When an LP is infeasible, the authors employ Farkas' Lemma to identify the specific constraints (and thus the simplices) that are causing the infeasibility. This "Certificate of Infeasibility Identifying" (CII) method allows for targeted subdivision of only the problematic simplices, rather than subdividing the entire domain. This is expected to lead to smaller LPs and faster convergence.
- Continuous Piecewise-Polynomial (CPP) vs. Continuous Differentiable Polynomial (CDP): The paper also discusses the implications of searching for CDP Lyapunov functions, which are more restrictive than CPP functions, and how the proposed methods apply to both.
Datasets
Not discussed in the paper. The paper focuses on a general methodology and uses a specific example polynomial vector field for demonstration.
Key Insights and Ideas
- Farkas' Lemma as a Diagnostic Tool: The clever application of Farkas' Lemma to identify the source of infeasibility in the LP is a significant insight. It transforms an unsolvable problem into a guided search, pinpointing exactly where the problem lies.
- Targeted Subdivision for Efficiency: The CII method's ability to subdivide only the "problematic" simplices is crucial. This avoids unnecessary computational overhead associated with subdividing parts of the domain that are already well-behaved, leading to more efficient triangulations.
- Convergence Guarantees: Proving the convergence of both the regular and the irregular (CII-based) subdivision algorithms is a critical theoretical contribution, ensuring that the methods will eventually find a solution if one exists within the specified degree constraints.
- CPP vs. CDP Trade-offs: The paper highlights that while CDP functions are more restrictive, the proposed methods can still be applied. However, for CPP functions, the adaptive subdivision can lead to significantly fewer variables and constraints, making it a more practical choice in many scenarios.
Key Results
- The paper proves the convergence of an algorithm for synthesizing continuous piecewise-polynomial Lyapunov functions using both regular and irregular (CII-based) subdivision strategies.
- An example demonstrates that the CII method can lead to a significant reduction in the number of variables and constraints compared to subdividing all simplices. For instance, in Example 19, the CII method resulted in a 91% improvement in the number of variables for a CPP Lyapunov function.
- The paper provides a comparison between synthesizing CPP and CDP Lyapunov functions, showing that for CPP functions, the CII method offers a notable advantage in terms of runtime and problem size.
Limitations and Future Work
- High Dimensions: The authors acknowledge that the tendencies observed in their comparisons (Table 1) have not been investigated on a comprehensive case study, and it is "of yet unknown whether the CII method is advantageous in high dimension."
- Sparsity in CDP: For CDP Lyapunov functions, the linear program offers no sparsity, which can be a limitation for very large problems. In contrast, CPP functions exhibit sparsity in their inequality matrices, which could be exploited by dedicated solvers.
- Future Research: The authors suggest that future research will address the gap between positive definite polynomials and polynomials admitting a Bernstein basis certifying collection. This implies exploring conditions under which a polynomial can be represented by a Bernstein basis with non-negative coefficients, which is crucial for the methods presented.
Summary updated