A sublinear algorithm for barrier-certificate-based data-driven model validation of dynamical systems

The paper considers the problem of scaling the method of barrier certificates for data-driven validation of dynamical system models using a large number of collected trajectories. Construction of a barrier certificate requires solving a convex feasibility problem that consists of a set of affine constraints whose number grows with the size of the dataset. The time complexity of traditional methods such as the interior-point method depends at least linearly on the size of the dataset and can be expensive to use for large datasets. We show that sublinear time complexity can be achieved using the multiplicative weights method, which was originally proposed to compute an approximate feasible solution for affine constraints. After modifications, the multiplicative weights method is able to yield an exact solution to the convex feasibility problem and hence a valid barrier certificate. We also present numerical studies and show that the multiplicative weights method is favorable to traditional methods for large datasets.