Optimization Online


A Scalable Algorithm for Sparse Portfolio Selection

Dimitris Bertsimas (dbertsim***at***mit.edu)
Ryan Cory-Wright (ryancw***at***mit.edu)

Abstract: 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.

Keywords: Sparse Portfolio Optimization, Binary Convex Optimization, Outer Approximation

Category 1: Integer Programming (Cutting Plane Approaches )

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Applications -- OR and Management Sciences (Finance and Economics )

Citation: @article{bertsimas2018scalable, title={A scalable algorithm for sparse portfolio selection}, author={Bertsimas, Dimitris and Cory-Wright, Ryan}, journal={arXiv preprint arXiv:1811.00138}, year={2018} }

Download: [PDF]

Entry Submitted: 10/31/2018
Entry Accepted: 10/31/2018
Entry Last Modified: 03/28/2021

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society