| Although cardinality constraints naturally arise in many applications, e.g., in portfolio selection problems of choosing small number of assets from a large pool of stocks or dynamic portfolio selection problems with limited trading dates within a given time horizon and in subset selection of the regression analysis, the state-of-the-art in cardinality constrained optimization has been stagnant up to this stage, largely due to the inherent combinatorial nature of such hard problems. We focus in this research on developing efficient and implementable solution algorithms for cardinality constrained optimization by investigating prominent structures and hidden properties of such problems. More specifically, we develop solution algorithms for four specific cardinality constrained optimization problems, including (i) the cardinality constrained linear-quadratic control problem, (ii) the optimal control problem of linear switched system with limited number of switching, (iii) the time cardinality constrained dynamic mean- variance portfolio selection problem, and (iv) cardinality constrained quadratic optimization problem. Taking advantages of a linear-quadratic structure of cardinality constrained optimization problems, we strive for analytical solutions when possible. More specifically, we derive an analytical solution for problem (iii) and obtain for both problems (i) and (ii) semi-analytical expressions of the solution governed by a family of Ricatti-like equations, which still suffer an exponentially growing complexity. To achieve high-performance of the solution algorithm, we devise algorithms of a branch and bound (BnB) type with various tight and computationally-cheap lower bounds achieved by identifying suitable SDP formulations and by exploiting geometric properties of the problem. We demonstrate efficiency of our proposed solution schemes evidenced from numerical experiments and present a firm step-forward in tackling this long-standing challenge of cardinality constrained optimization. |
