A Scalable Algorithm for Sparse Portfolio Selection

The sparse portfolio selection problem is one of the most famous and frequently studied problems in the optimization and financial economics literatures. In a universe of risky assets, the goal is to construct a portfolio with maximal expected return and minimum variance, subject to an upper bound on the number of positions, linear inequalities, and minimum investment constraints. Existing certifiably optimal approaches to this problem have not been shown to converge within a practical amount of time at real-world problem sizes with more than 400 securities. In this paper, we propose a more scalable approach. By imposing a ridge regularization term, we reformulate the problem as a convex binary optimization problem, which is solvable via an efficient outer-approximation procedure. We propose various techniques for improving the performance of the procedure, including a heuristic that supplies high-quality warm-starts, and a second heuristic for generating additional cuts that strengthens the root relaxation. We also study the problem’s continuous relaxation, establish that it is second-order cone representable, and supply a sufficient condition for its tightness. In numerical experiments, we establish that a conjunction of the imposition of ridge regularization and the use of the outer-approximation procedure gives rise to dramatic speedups for sparse portfolio selection problems. Summary of Contribution: This paper proposes a new decomposition scheme for tackling the problem of sparse portfolio selection: the problem of selecting a limited number of securities in a portfolio. This is a challenging problem to solve in high dimensions, as it belongs to the class of mixed-integer, nonseparable nonlinear optimization problems. We propose a new Benders-type cutting plane method and demonstrate its efficacy on a wide set of both synthetic and real-world problems, including problems with thousands of securities. Our approach also provides insights for other mixed-integer optimization problems with logical constraints.