Optimal Cardinality Constrained Portfolio Selection

One long-standing challenge in both the optimization and investment communities is to devise an efficient algorithm to select a small number of assets from an asset pool such that a portfolio objective is optimized. This cardinality constrained investment situation naturally arises due to the presence of various forms of market friction, such as transaction costs and management fees, or even due to the consideration of mental cost. Unfortunately, the combinatorial nature of such a portfolio selection problem formulation makes the exact solution process NP-hard in general. We focus in this paper on the cardinality constrained mean-variance portfolio selection problem. Instead of tailoring such a difficult problem into the general solution framework of mixed-integer programming formulation, we explore the special structures and rich geometric properties behind the mathematical formulation. Applying the Lagrangian relaxation to the primal problem results in a pure cardinality constrained portfolio selection problem, which possesses a symmetric property, and to which geometric approaches can be developed. Different from the existing literature that has primarily focused on some direct relaxations of the cardinality constraint, we consider modifying the objective function to some separable relaxations, which are immune to the hard cardinality constraint. More specifically, we develop efficient lower bounding schemes by using the circumscribed box, the circumscribed ball, and the circumscribed axis-aligned ellipsoid to approximate the objective contour of the problem. In particular, all these cardinality constrained relaxation problems can be solved analytically. Furthermore, we derive efficient polynomial-time algorithms for the corresponding dual search problems. Most promisingly, the lower bounding scheme using the circumscribed axis-aligned ellipsoid leads to a semidefinite programming (SDP) formulation and offers a sharp bound and high-quality feasible solution. By integrating these lower bounding schemes into a branch-and-bound algorithm (BnB), our solution scheme outperforms CPLEX significantly in identifying the exact optimal portfolio.