Learning Lyapunov Functions for Hybrid Systems
Learning Lyapunov Functions for Hybrid Systems
复制标题
DOI：
10.1145/3447928.3456644
复制
发表时间：
2020-12
期刊：
影响因子：
--
通讯作者：
Shaoru Chen;Mahyar Fazlyab;M. Morari;George Pappas;V. Preciado
中科院分区：
文献类型：
--
作者：
Shaoru Chen;Mahyar Fazlyab;M. Morari;George Pappas;V. Preciado
我们提出了一种基于采样的方法来学习一类离散时间自治混合系统，允许混合整数表示的李雅普诺夫函数。这些系统包括自治分段仿射系统，具有模型预测控制器的线性系统的闭环动态，具有ReLU神经网络控制器的反馈中的分段仿射/线性互补/混合逻辑动态系统等。所提出的方法包括学习者和验证者之间的交替，以在Lyapunov函数候选者的凸集内找到有效的Lyapunov函数。在每次迭代中，学习器使用状态样本的集合通过参数空间中的凸规划来选择李雅普诺夫函数候选。然后，验证器在状态空间中求解混合整数二次规划，以验证所提出的李雅普诺夫函数候选者或用反例拒绝它，即，李雅普诺夫条件失效的状态。然后，将该反例添加到学习器的样本集，以细化李雅普诺夫函数候选集。通过根据凸优化的解析中心割平面方法设计学习器和验证器，我们表明，当有效的李雅普诺夫函数集在参数空间中是全维的，我们的方法找到一个有效的李雅普诺夫函数在有限的步骤。我们证明了我们的稳定性分析方法的闭环MPC动态系统和ReLU神经网络控制的PWA系统。
We propose a sampling-based approach to learn Lyapunov functions for a class of discrete-time autonomous hybrid systems that admit a mixed-integer representation. Such systems include autonomous piecewise affine systems, closed-loop dynamics of linear systems with model predictive controllers, piecewise affine/linear complementarity/mixed-logical dynamical system in feedback with a ReLU neural network controller, etc. The proposed method comprises an alternation between a learner and a verifier to find a valid Lyapunov function inside a convex set of Lyapunov function candidates. In each iteration, the learner uses a collection of state samples to select a Lyapunov function candidate through a convex program in the parameter space. The verifier then solves a mixed-integer quadratic program in the state space to either validate the proposed Lyapunov function candidate or reject it with a counterexample, i.e., a state where the Lyapunov condition fails. This counterexample is then added to the sample set of the learner to refine the set of Lyapunov function candidates. By designing the learner and the verifier according to the analytic center cutting-plane method from convex optimization, we show that when the set of valid Lyapunov functions is full-dimensional in the parameter space, our method finds a valid Lyapunov function in a finite number of steps. We demonstrate our stability analysis method on closed loop MPC dynamical systems and a ReLU neural network controlled PWA system.