A Scalable Algorithm for Sparse Portfolio Selection
<jats:p> 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 a...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Institute for Operations Research and the Management Sciences (INFORMS)
2022
|
| Online Access: | https://hdl.handle.net/1721.1/144103 |
| _version_ | 1826201205519417344 |
|---|---|
| author | Bertsimas, Dimitris Cory-Wright, Ryan |
| author2 | Sloan School of Management |
| author_facet | Sloan School of Management Bertsimas, Dimitris Cory-Wright, Ryan |
| author_sort | Bertsimas, Dimitris |
| collection | MIT |
| description | <jats:p> 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. </jats:p><jats:p> 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. </jats:p> |
| first_indexed | 2024-09-23T11:48:11Z |
| format | Article |
| id | mit-1721.1/144103 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:48:11Z |
| publishDate | 2022 |
| publisher | Institute for Operations Research and the Management Sciences (INFORMS) |
| record_format | dspace |
| spelling | mit-1721.1/1441032023-12-07T14:47:21Z A Scalable Algorithm for Sparse Portfolio Selection Bertsimas, Dimitris Cory-Wright, Ryan Sloan School of Management Massachusetts Institute of Technology. Operations Research Center <jats:p> 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. </jats:p><jats:p> 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. </jats:p> 2022-07-27T18:35:34Z 2022-07-27T18:35:34Z 2022 2022-07-27T18:24:59Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/144103 Bertsimas, Dimitris and Cory-Wright, Ryan. 2022. "A Scalable Algorithm for Sparse Portfolio Selection." INFORMS Journal on Computing, 34 (3). en 10.1287/IJOC.2021.1127 INFORMS Journal on Computing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute for Operations Research and the Management Sciences (INFORMS) arXiv |
| spellingShingle | Bertsimas, Dimitris Cory-Wright, Ryan A Scalable Algorithm for Sparse Portfolio Selection |
| title | A Scalable Algorithm for Sparse Portfolio Selection |
| title_full | A Scalable Algorithm for Sparse Portfolio Selection |
| title_fullStr | A Scalable Algorithm for Sparse Portfolio Selection |
| title_full_unstemmed | A Scalable Algorithm for Sparse Portfolio Selection |
| title_short | A Scalable Algorithm for Sparse Portfolio Selection |
| title_sort | scalable algorithm for sparse portfolio selection |
| url | https://hdl.handle.net/1721.1/144103 |
| work_keys_str_mv | AT bertsimasdimitris ascalablealgorithmforsparseportfolioselection AT corywrightryan ascalablealgorithmforsparseportfolioselection AT bertsimasdimitris scalablealgorithmforsparseportfolioselection AT corywrightryan scalablealgorithmforsparseportfolioselection |