IEEE Transactions on Automatic Control, Vol.56, No.8, 1936-1941, 2011
Cardinality Constrained Linear-Quadratic Optimal Control
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.
Keywords:Branch-and-bound (BnB);cardinality constraint;dynamic programming;linear-quadratic (LQ) control;quadratic programming;semidefinite programming (SDP);setup cost