Convex Certificates for Model (In)validation of Switched Affine Systems with Unknown Switches

N. Ozay, M. Sznaier and C. M. Lagoa
IEEE Transactions on Automatic Control, November, 2014.

Checking validity of a model is a crucial step in the process of system identification. This is especially true when dealing with switched affine systems since, in this case, the problem of system identification from noisy data is known to be generically NP-Hard and can only be solved in practice by using heuristics and relaxations. Therefore, before the identified models can be used for instance for controller design, they should be systematically validated against additional experimental data. In this paper we address the problem of model (in)validation for multi-input multi-output switched affine autoregressive exogenous systems with unknown switches. As a first step, we prove that necessary and sufficient invalidation certificates can be obtained by solving a sequence of convex optimization problems. In principle, these problems involve increasingly large matrices. However, as we show in the paper by exploiting recent results from semi-algebraic geometry, the proposed algorithm is guaranteed to stop after a finite number of steps that can be be explicitly computed from the a-priori information. In addition, this algorithm exploits the sparse structure of the underlying optimization problem to substantially reduce the computational burden. The effectiveness of the proposed method is illustrated using both academic examples and a non-trivial problem arising in computer vision: activity monitoring.