论文标题
线性系统可控性的零态距离：复杂性，边界和算法
Zero-Norm Distance to Controllability of Linear Systems: Complexity, Bounds, and Algorithms
论文作者
论文摘要
过去已经对可控系统的可控系统与一组不可控制的系统之间的距离进行了广泛的研究。但是，很少考虑相反的方向，即确定无法控制的系统与可控系统集之间的“距离”。在本文中，我们通过将零符号距离与可控性（ZnDC）的概念定义为系统矩阵中最少的条目（参数），以解决此问题，以使原始系统可控制。我们在此问题中表明存在通用性，因此该概念中采用的其他矩阵规范（例如$ 2 $ - 纳尔或Frobenius Norm）是胡说八道。对于ZnDC，我们表明它是NP螺栓的计算，即使只有状态矩阵才能受到干扰。然后，我们提供一些非平凡的下限和上限。为了计算，我们提供了两种启发式算法。第一个是将ZnDC转换为线性参数化系统的结构可控性问题，然后根据适当的目标函数贪婪地选择候选链接。第二个是基于加权$ L_1 $ -NOMM弛豫和凸环过程，该过程是为ZnDC量身定制的，当时涉及扰动参数时。最后，我们研究了我们在多代理系统中几个典型的不可控制网络中提出的算法的性能。
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 $l_1$-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.
