Paper Info
Title
Sparsest Feedback Selection for Structurally Cyclic Systems with Dedicated Actuators and Sensors in Polynomial Time
Abstract
This paper deals with optimal feedback selection problem in linear time-invariant (LTI) structured systems for arbitrary pole placement, an important open problem in structured systems. Specifically, we solve the <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">sparsest feedback selection</italic> problem for LTI structured systems. In this paper, we consider <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">structurally cyclic</italic> systems with <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">dedicated</italic> inputs and outputs. For this class of systems, we prove that the sparsest feedback selection problem is equivalent to the strong connectivity augmentation problem in graph theory. We present an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(n^2)$</tex-math></inline-formula> algorithm to find a sparsest feedback matrix for structured systems when every state is actuated by a dedicated input and every state is sensed by a dedicated output, where <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$n$</tex-math></inline-formula> denotes the number of states in the system. If the inputs and the outputs are such that not every state is actuated by a dedicated input and/or not every state is sensed by a dedicated output, then we provide an <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$O(n^3)$</tex-math></inline-formula> algorithm for the sparsest feedback selection problem. These results show that sparsest feedback selection with dedicated i/o is a specific case of the optimal feedback selection problem that is solvable in polynomial time. We later analyze the sparsest feedback selection problem for structurally cyclic systems when both the input and the output are dedicated and the feedback pattern is <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">constrained</italic> . When some of the feedback links are forbidden, we prove that the problem is NP-hard. The results in this paper along with the previously known results conclude that the optimal feedback selection problem is polynomial-time solvable only for the dedicated input–output case without forbidden feedback links and also without weights for the feedback links.
Year
DOI
Venue
2019
10.1109/tac.2019.2891048
IEEE Transactions on Automatic Control
Keywords
Field
DocType
Heuristic algorithms,NP-hard problem,Actuators,Sensor systems,Linear systems
Graph theory,Mathematical optimization,Open problem,Linear system,Matrix (mathematics),Full state feedback,Structured systems,Time complexity,Mathematics,Actuator
Journal
Volume
Issue
ISSN
64
9
0018-9286
Citations 
PageRank 
References 
0
0.34
0
Authors
3
Name
Order
Citations
PageRank
Shana Moothedath111.71
Prasanna Chaporkar221925.60
Madhu N. Belur33713.87