Cardinality Constrained Linear-Quadratic Optimal Control

Abstract

As control implementation often incurs not only a variable cost associated with the magnitude or energy of the control, but also a setup cost, we consider a discrete-time linear-quadratic (LQ) optimal control problem with a limited number of control implementations, termed in this technical note the cardinality constrained linear-quadratic optimal control (CCLQ). We first derive a semi-analytical feedback policy for CCLQ problems using dynamic programming (DP). Due to the exponential growth of the complexity in calculating the action regions, however, DP procedure is only efficient for CCLQ problems with a scalar state space. Recognizing this fact, we develop then two lower-bounding schemes and integrate them into a branch-and-bound (BnB) solution framework to offer an efficient algorithm in solving general CCLQ problems. Adopting the devised solution algorithm for CCLQ problems, we can solve efficiently the linear-quadratic optimal control problem with setup costs.