2022/09/06 by Yuan Zhang, Yuanqing Xia, Zhang, Yuan +5 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · Engineering · Mathematics · #Algorithm #Applied mathematics #Computation #Computer science #Controllability #Discrete mathematics #Distributed Control Multi-Agent Systems #FOS: Electrical engineering #FOS: Mathematics #Gene Regulatory Network Analysis #Linear system #Mathematical analysis #Mathematical optimization #Mathematics #Matrix (chemical analysis) #Matrix norm #Norm (philosophy) #Optimization and Control (math.OC) #Parameterized complexity #Stability and Control of Uncertain Systems #Systems and Control (eess.SY) #electronic engineering #information engineering
paper · pdf · doi:10.48550/arxiv.2209.02212
published in arXiv (Cornell University) (Cornell University)
openalex publication_date 2022/09/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
Determining the distance between a controllable system to the set of uncontrollable systems, namely, the controllability radius problem, has been extensively studied in the past. However, the opposite direction, that is, determining the `distance' between an uncontrollable system to the set of controllable systems, has seldom been considered. In this paper, we address this problem by defining the notion of zero-norm distance to controllability (ZNDC) to be the smallest number of entries (parameters) in the system matrices that need to be perturbed to make the original system controllable. We show genericity exists in this problem, so that other matrix norms (such as the 2-norm or the Frobenius norm) adopted in this notion are nonsense. For ZNDC, we show it is NP-hard to compute, even when only the state matrix can be perturbed. We then provide some nontrivial lower and upper bounds. For its computation, we provide two heuristic algorithms. The first one is by transforming the ZNDC into a problem of structural controllability of linearly parameterized systems, and then greedily selecting the candidate links according to a suitable objective function. The second one is based on the weighted l1-norm relaxation and the convex-concave procedure, which is tailored for ZNDC when additional structural constraints are involved in the perturbed parameters. Finally, we examine the performance of our proposed algorithms in several typical uncontrollable networks in multi-agent systems.