.png){kind=icon}
返回
Minimum Cost Feedback Selection in Structured Systems: Hardness and Approximation Algorithm
.png){kind=icon}
OA
AI
DOI：10.1109/TAC.2020.3004789.png)
.png){kind=icon}
.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
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.
Keyword:
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
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
IF:
7
论文数:
1.3W
被引数:
6.7W
机构
引用论文
暂无论文信息