Global optimization for low-dimensional switching linear regression and bounded-error estimation

The paper provides global optimization algorithms for two particularly\ndifficult nonconvex problems raised by hybrid system identification: switching\nlinear regression and bounded-error estimation. While most works focus on local\noptimization heuristics without global optimality guarantees or with guarantees\nvalid only under restrictive conditions, the proposed approach always yields a\nsolution with a certificate of global optimality. This approach relies on a\nbranch-and-bound strategy for which we devise lower bounds that can be\nefficiently computed. In order to obtain scalable algorithms with respect to\nthe number of data, we directly optimize the model parameters in a continuous\noptimization setting without involving integer variables. Numerical experiments\nshow that the proposed algorithms offer a higher accuracy than convex\nrelaxations with a reasonable computational burden for hybrid system\nidentification. In addition, we discuss how bounded-error estimation is related\nto robust estimation in the presence of outliers and exact recovery under\nsparse noise, for which we also obtain promising numerical results.\n