Matroid-Constrained Approximately Supermodular Optimization for Near-Optimal Actuator Scheduling
Matroid-Constrained Approximately Supermodular Optimization for Near-Optimal Actuator Scheduling
复制标题
用于近乎最优执行器调度的拟阵约束近似超模优化
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Alejandro Ribeiro
中科院分区：
文献类型：
--
作者：
Luiz F. O. Chamon;Alexandre Amice;Alejandro Ribeiro
本文研究了线性二次型调节器（LQR）目标最小化的执行器调度问题。一般来说，这个问题是NP难的，因此即使对于中等规模的系统，它的解也只能近似。虽然凸松弛已被用来获得这些近似，他们不来与性能保证。另一种常见的方法是使用贪婪搜索。尽管如此，经典的保证并不适用于调度问题，因为LQR成本函数既不是次模也不是超模。虽然替代的超模品质因数，如可控性Gramian的log det，经常被用作解决方案，但由此产生的问题并不等同于原始的LQR问题。这项工作表明，不需要改变原来的问题，以获得性能保证。具体来说，它证明了LQR成本函数是近似超模的，并为这些函数在一般拟阵上的贪婪最小化提供了新的近最优性证明。这些证书被证明接近经典的1/2保证的超模函数在相关的应用场景。
This work considers the problem of scheduling actuators to minimize the Linear Quadratic Regulator (LQR) objective. In general, this problem is NP-hard and its solution can therefore only be approximated even for moderately large systems. Although convex relaxations have been used to obtain these approximations, they do not come with performance guarantees. Another common approach is to use greedy search. Still, classical guarantees do not hold for the scheduling problem because the LQR cost function is neither submodular nor supermodular. Though surrogate supermodular figures of merit, such as the log det of the controllability Gramian, are often used as a workaround, the resulting problem is not equivalent to the original LQR one. This work shows that no change to the original problem is needed to obtain performance guarantees. Specifically, it proves that the LQR cost function is approximately supermodular and provides new near-optimality certificates for the greedy minimization of these functions over a generic matroid. These certificates are shown to approach the classical 1/2 guarantee of supermodular functions in relevant application scenarios.
具有保证性能范围的确定性和随机执行器调度
影响因子：
6.8
作者：
Siami, Milad;Olshevsky, Alexander;Jadbabaie, Ali
通讯作者：
Jadbabaie, Ali