Matroid-constrained approximately supermodular optimization for near-optimal actuator scheduling


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.

IEEE Conference on Decision and Control