# A Scalable Algorithm For Sparse Portfolio Selection

arXiv: https://arxiv.org/abs/1811.00138 · HTML: https://mlsanity.com/paper/1811.00138/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2018.

## Built on by (most cited first, 8 of 8)

- [Evolving Scientific Discovery by Unifying Data and Background Knowledge with AI Hilbert](https://mlsanity.com/paper/2308.09474/) (2023)
- [Principal Component Hierarchy for Sparse Quadratic Programs](https://mlsanity.com/paper/2105.12022/) (2021)
- [Autonomous Sparse Mean-CVaR Portfolio Optimization](https://mlsanity.com/paper/2405.08047/) (2024)
- [Large-scale Time-Varying Portfolio Optimisation using Graph Attention Networks](https://mlsanity.com/paper/2407.15532/) (2024)
- [Efficient Cross-Validation for Sparse Linear Regression](https://mlsanity.com/paper/2306.14851/) (2023)
- [A Scalable Gradient-Based Optimization Framework for Sparse Minimum-Variance Portfolio Selection](https://mlsanity.com/paper/2505.10099/) (2025)
- [Integrated Prediction and Multi-period Portfolio Optimization](https://mlsanity.com/paper/2512.11273/) (2025)
- [Sparsity Regularized and Robust Mean Variance Portfolio Selection Under Ellipsoidal Uncertainty](https://mlsanity.com/paper/2609.11749/) (2026)

## Abstract (arXiv)

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 do not 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 which supplies high-quality warm-starts, a preprocessing technique for decreasing the gap at the root node, and an analytic technique for strengthening our cuts. We also study the problem's Boolean relaxation, establish that it is second-order-cone representable, and supply a sufficient condition for its tightness. In numerical experiments, we establish that the outer-approximation procedure gives rise to dramatic speedups for sparse portfolio selection problems.