A Sublinear Algorithm for Barrier-Certificate-Based Data-Driven Model Validation of Dynamical Systems
Shuo Han, Topcu Ufuk, George Pappas

Citation
Shuo Han, Topcu Ufuk, George Pappas. "A Sublinear Algorithm for Barrier-Certificate-Based Data-Driven Model Validation of Dynamical Systems". Conference on Decision and Control, IEEE, 15, December, 2015.

Abstract
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.

Electronic downloads

Internal. This publication has been marked by the author for TerraSwarm-only distribution, so electronic downloads are not available without logging in.

Citation formats

• HTML

  Shuo Han, Topcu Ufuk, George Pappas. <a
  href="http://www.terraswarm.org/pubs/524.html"
  >A Sublinear Algorithm for Barrier-Certificate-Based
  Data-Driven Model Validation of Dynamical Systems</a>,
  Conference on Decision and Control, IEEE, 15, December, 2015.

• Plain text

  Shuo Han, Topcu Ufuk, George Pappas. "A Sublinear
  Algorithm for Barrier-Certificate-Based Data-Driven Model
  Validation of Dynamical Systems". Conference on
  Decision and Control, IEEE, 15, December, 2015.

• BibTeX

  @inproceedings{HanUfukPappas15_SublinearAlgorithmForBarrierCertificateBasedDataDriven,
      author = {Shuo Han and Topcu Ufuk and George Pappas},
      title = {A Sublinear Algorithm for
                Barrier-Certificate-Based Data-Driven Model
                Validation of Dynamical Systems},
      booktitle = {Conference on Decision and Control},
      organization = {IEEE},
      day = {15},
      month = {December},
      year = {2015},
      abstract = {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.},
      URL = {http://terraswarm.org/pubs/524.html}
  }
  

Posted by Barb Hoversten on 25 Mar 2015.
Groups: services