A sublinear algorithm for barrier-certificate-based data-driven model validation of dynamical systems
A sublinear algorithm for barrier-certificate-based data-driven model validation of dynamical systems
复制标题
用于动力系统基于障碍证书的数据驱动模型验证的次线性算法
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
George Pappas
中科院分区：
文献类型：
--
作者：
Shuo Han;U. Topcu;George Pappas
本文考虑了使用大量收集的轨迹来扩展用于动力系统模型的数据驱动验证的障碍证书方法的问题。构建障碍证书需要解决凸可行性问题，该问题由一组仿射约束组成，其数量随着数据集的大小而增长。传统方法（例如内点法）的时间复杂度至少线性地取决于数据集的大小，并且对于大型数据集来说使用起来可能会很昂贵。我们证明，可以使用乘法权重方法来实现次线性时间复杂度，该方法最初是为了计算仿射约束的近似可行解而提出的。经过修改后，乘法权重方法能够产生凸可行性问题的精确解，从而产生有效的障碍证书。我们还提出了数值研究，并表明乘法权重方法对于大型数据集优于传统方法。
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.