November 3, 2006
Motivated by questions in robust control and switched linear dynamical systems, we consider the problem checking whether all convex combinations of k matrices in R^{n x n} are stable. In particular, we are interested whether there exist algorithms which can solve this problem in time polynomial in n and k. We show that if $k= \lceil n^d \rceil$ for any fixed real d>0, then the problem is NP-hard, meaning that no polynomial-time algorithm in n exists provided that P is not NP, a widely believed conjecture in computer science. On the other hand, when k is a constant independent of n, then it is known that the problem may be solved in polynomial time in n. Using these results and the method of measurable switching rules, we prove our main statement: verifying the absolute asymptotic stability of a continuous-time switched linear system with more than n^d matrices A_i in R^{n x n} satisfying 0 >= A_i + A_i^{T} is NP-hard.
Similar papers 1
October 7, 2013
We survey the problem of deciding the stability or stabilizability of uncertain linear systems whose region of uncertainty is a polytope. This natural setting has applications in many fields of applied science, from Control Theory to Systems Engineering to Biology. We focus on the algorithmic decidability of this property when one is given a particular polytope. This setting gives rise to several different algorithmic questions, depending on the nature of time (discrete/conti...
June 10, 2012
In this note we prove NP-hardness of the following problem: Given a set of matrices, is there a convex combination of those that is a nonsingular M-matrix? Via known characterizations of M-matrices, our result establishes NP-hardness of several fundamental problems in systems analysis and control, such as testing the instability of an uncertain dynamical system, and minimizing the spectral radius of an affine matrix function.
July 21, 2012
We describe new methods for deciding the stability of switching systems. The methods build on two ideas previously appeared in the literature: the polytope norm iterative construction, and the lifting procedure. Moreover, the combination of these two ideas allows us to introduce a pruning algorithm which can importantly reduce the computational burden. We prove several appealing theoretical properties of our methods like a finiteness computational result which extends a known...
February 23, 2002
This paper gives a necessary and sufficient condition for robust D-stability of Polytopic Polynomial Matrices. Edge theorem is extended to multi-input-multi-output case.
April 15, 2015
We show that for any positive integer $d$, there are families of switched linear systems---in fixed dimension and defined by two matrices only---that are stable under arbitrary switching but do not admit (i) a polynomial Lyapunov function of degree $\leq d$, or (ii) a polytopic Lyapunov function with $\leq d$ facets, or (iii) a piecewise quadratic Lyapunov function with $\leq d$ pieces. This implies that there cannot be an upper bound on the size of the linear and semidefinit...
October 31, 2020
This paper deals with stability of discrete-time switched linear systems whose all subsystems are unstable. We present sufficient conditions on the subsystems matrices such that a switched system is globally exponentially stable under a set of purely time-dependent switching signals that are allowed to activate all subsystems. The main apparatuses for our analysis are (matrix) commutation relations between certain products of the subsystems matrices and graph-theoretic argume...
March 9, 2018
Can we conclude the stability of an unknown dynamical system from the knowledge of a finite number of snapshots of trajectories? We tackle this black-box problem for switched linear systems. We show that, for any given random set of observations, one can give probabilistic stability guarantees. The probabilistic nature of these guarantees implies a trade-off between their quality and the desired level of confidence. We provide an explicit way of computing the best stability-l...
January 10, 2012
We study the stability and stabilizability of a continuous-time switched control system that consists of the time-invariant $n$-dimensional subsystems \dot{x}=A_ix+B_i(x)u\quad (x\in\mathbb{R}^n, t\in\mathbb{R}_+ \textrm{and} u\in\mathbb{R}^{m_i}),\qquad \textrm{where} i\in{1,...,N} and a switching signal $\sigma(\bcdot)\colon\mathbb{R}_+\rightarrow{1,...,N}$ which orchestrates switching between these subsystems above, where $A_i\in\mathbb{R}^{n\times n}, n\ge1, N\ge2, m_i\ge...
April 7, 2016
Many problems in systems and control theory can be formulated in terms of robust D-stability analysis, which aims at verifying if all the eigenvalues of an uncertain matrix lie in a given region D of the complex plane. Robust D-stability analysis is an NP-hard problem and many polynomial-time algorithms providing either sufficient or necessary conditions for an uncertain matrix to be robustly D-stable have been developed in the past decades. Despite the vast literature on the...
May 12, 2018
We study the following optimization problem over a dynamical system that consists of several linear subsystems: Given a finite set of $n\times n$ matrices and an $n$-dimensional vector, find a sequence of $K$ matrices, each chosen from the given set of matrices, to maximize a convex function over the product of the $K$ matrices and the given vector. This simple problem has many applications in operations research and control, yet a moderate-sized instance is challenging to so...