  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 Lyapunov functions is full-dimensional in the
parameter space, our method finds a 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.
