Minimum Cost Feedback Selection in Structured Systems: Hardness and Approximation Algorithm

作     者：Joshi, Aishwary Moothedath, Shana Chaporkar, Prasanna 

作者机构：QE Secur LLP Gurugram 122002 India Univ Washington Seattle WA 98195 USA Indian Inst Technol Dept Elect Engn Mumbai 400076 Maharashtra India 

出 版 物：《IEEE TRANSACTIONS ON AUTOMATIC CONTROL》 (IEEE自动控制汇刊)

年 卷 期：2020年第65卷第12期

页      面：5517-5524页

核心收录：

学科分类：0808[工学-电气工程] 08[工学] 0811[工学-控制科学与工程] 

主　　题：Approximation algorithms Optimization Closed loop systems Dynamic programming Heuristic algorithms Dynamical systems Linear systems Arbitrary pole-placement hierarchical networks linear dynamical systems minimum cost feedback selection 

摘      要：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 logn-approximate solution. For hierarchical networks, we give a dynamic programming based algorithm to obtain an optimal solution in polynomial time.