Back to Search
Start Over
Minimum Cost Feedback Selection in Structured Systems: Hardness and Approximation Algorithm.
- Source :
-
IEEE Transactions on Automatic Control . Dec2020, Vol. 65 Issue 12, p5517-5524. 8p. - Publication Year :
- 2020
-
Abstract
- This article deals with output feedback selection in linear time-invariant structured systems. We assume that the inputs and the outputs are dedicated, i.e., each input directly actuates a single state and each output directly senses a single state. Given a structured system with dedicated inputs and outputs and a cost matrix that denotes the cost of each feedback connection, our aim is to select a minimum cost set of feedback connections such that the closed-loop system satisfies arbitrary pole-placement. This problem is referred to as the optimal feedback selection problem for dedicated i/o. The optimal feedback selection problem for dedicated i/o is NP-hard and inapproximable to a constant factor of log n, where n denotes the system dimension. To this end, we propose an algorithm to find an approximate solution to the problem. The proposed algorithm consists of a potential function incorporated with a greedy scheme and attains a solution with a guaranteed approximation ratio. We consider two special network topologies of practical importance, referred to as back-edge feedback structure and hierarchical networks. For the first case, which is NP-hard and inapproximable to a multiplicative factor of log n, we provide a log n-approximate solution. For hierarchical networks, we give a dynamic programming based algorithm to obtain an optimal solution in polynomial time. [ABSTRACT FROM AUTHOR]
Details
- Language :
- English
- ISSN :
- 00189286
- Volume :
- 65
- Issue :
- 12
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Automatic Control
- Publication Type :
- Periodical
- Accession number :
- 147401484
- Full Text :
- https://doi.org/10.1109/TAC.2020.3004789