Minimal Perturbations for Zero Controllability of Discrete-Time Linear Systems: Complexity Analysis

• 成果类型: Article
• 署名作者: Dey, Priyanka; Balachandran, Niranjan
• 署名单位: Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Bombay; Indian Institute of Technology System (IIT System); Indian Institute of Technology (IIT) - Bombay
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2020.2995185
• 发表日期: 2021
• 页码: 1391-1398
• 关键词: Controllability; Linear systems; Perturbation methods; Complexity theory; large-scale systems; resilience; Feedback arc set; generic zero controllability; perturbations

摘要

This article deals with computational complexity of various problems related to the zero controllability of a discrete-time linear time-invariant system, assuming that purely structural conditions at the level of the connections between the system states (i.e., state-connections) and the connections from the inputs to the states (i.e., input-connections) are known. Given a generically zero controllable system, we consider the following problems: i) find a minimal set of input-connections whose removal makes the resulting system not generic zero controllability; ii) identify a minimal cost set of input-connections that must be retained from the given set of input-connections while preserving generic zero controllability property; and iii) given a not generically zero controllable system, find a smallest set of state-connections whose removal makes the resulting system generically zero controllable. Problem i) is polynomially solvable. Problems ii) and iii) are NP-hard and approximation results are provided for them. The results of i) and iii) provide clues to analyze the fragility and hardness involved in modifying a system structure. Problem ii) is useful to ensure an accurate discrete-time linear approximation of a large-scale system by maintaining generic zero controllability of the linear system.