Cardinality constrained linear-quadratic optimal control: Lower bounding scheme via scalar state space by semidefinite programming

This paper considers a discrete-time linear- quadratic optimal control problem with a limited number of control implementation, which is termed as the cardinality constrained linear-quadratic optimal control problem (CCLQ). Derivation of a powerful solution method for CCLQ plays an essential role in developing an efficient solution scheme for linear-quadratic optimal control problems with set-up costs. As dynamic programming offers an analytical solution for CCLQ with a scalar state space (sCCLQ), we develop in this paper a solution scheme to appropriately construct an sCCLQ problem to provide a tight lower bound of the primal CCLQ with a vector state space by semidefinite programming (SDP). Integrating this lower bounding scheme into a branch-and- bound solution framework, general CCLQ problems can be solved efficiently.