IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v61y2013i3p745-761.html
   My bibliography  Save this article

Optimal Cardinality Constrained Portfolio Selection

Author

Listed:
  • Jianjun Gao

    (Department of Automation, Shanghai Jiao Tong University, Shanghai, China)

  • Duan Li

    (Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong)

Abstract

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.

Suggested Citation

  • Jianjun Gao & Duan Li, 2013. "Optimal Cardinality Constrained Portfolio Selection," Operations Research, INFORMS, vol. 61(3), pages 745-761, June.
  • Handle: RePEc:inm:oropre:v:61:y:2013:i:3:p:745-761
    DOI: 10.1287/opre.2013.1170
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2013.1170
    Download Restriction: no

    File URL: https://libkey.io/10.1287/opre.2013.1170?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. Duan Li & Xiaoling Sun, 2006. "Nonlinear Integer Programming," International Series in Operations Research and Management Science, Springer, number 978-0-387-32995-6, March.
    2. P. Bonami & M. A. Lejeune, 2009. "An Exact Solution Approach for Portfolio Optimization Problems Under Stochastic and Integer Constraints," Operations Research, INFORMS, vol. 57(3), pages 650-670, June.
    3. Ledoit, Olivier & Wolf, Michael, 2003. "Improved estimation of the covariance matrix of stock returns with an application to portfolio selection," Journal of Empirical Finance, Elsevier, vol. 10(5), pages 603-621, December.
    4. Duan Li & Wan‐Lung Ng, 2000. "Optimal Dynamic Portfolio Selection: Multiperiod Mean‐Variance Formulation," Mathematical Finance, Wiley Blackwell, vol. 10(3), pages 387-406, July.
    5. Jianjun Gao & Duan Li, 2013. "A polynomial case of the cardinality-constrained quadratic optimization problem," Journal of Global Optimization, Springer, vol. 56(4), pages 1441-1455, August.
    6. Ravi Jagannathan & Tongshu Ma, 2003. "Risk Reduction in Large Portfolios: Why Imposing the Wrong Constraints Helps," Journal of Finance, American Finance Association, vol. 58(4), pages 1651-1683, August.
    7. Pierre Bonami & Miguel A. Lejeune, 2009. "An Exact Solution Approach for Integer Constrained Portfolio Optimization Problems Under Stochastic Constraints," Post-Print hal-00421756, HAL.
    8. Duan Li & Xiaoling Sun & Jun Wang, 2006. "Optimal Lot Solution To Cardinality Constrained Mean–Variance Formulation For Portfolio Selection," Mathematical Finance, Wiley Blackwell, vol. 16(1), pages 83-101, January.
    9. Costa, O. L. V. & Paiva, A. C., 2002. "Robust portfolio selection using linear-matrix inequalities," Journal of Economic Dynamics and Control, Elsevier, vol. 26(6), pages 889-909, June.
    10. Dimitris Bertsimas & Romy Shioda, 2009. "Algorithm for cardinality-constrained quadratic optimization," Computational Optimization and Applications, Springer, vol. 43(1), pages 1-22, May.
    11. Chiu, Mei Choi & Li, Duan, 2006. "Asset and liability management under a continuous-time mean-variance optimization framework," Insurance: Mathematics and Economics, Elsevier, vol. 39(3), pages 330-355, December.
    12. B. Blog & G. van der Hoek & A. H. G. Rinnooy Kan & G. T. Timmer, 1983. "The Optimal Selection of Small Portfolios," Management Science, INFORMS, vol. 29(7), pages 792-798, July.
    13. repec:bla:jfinan:v:58:y:2003:i:4:p:1651-1684 is not listed on IDEAS
    14. Victor DeMiguel & Francisco J. Nogales, 2009. "Portfolio Selection with Robust Estimation," Operations Research, INFORMS, vol. 57(3), pages 560-577, June.
    15. D. Goldfarb & G. Iyengar, 2003. "Robust Portfolio Selection Problems," Mathematics of Operations Research, INFORMS, vol. 28(1), pages 1-38, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Carina Moreira Costa & Dennis Kreber & Martin Schmidt, 2022. "An Alternating Method for Cardinality-Constrained Optimization: A Computational Study for the Best Subset Selection and Sparse Portfolio Problems," INFORMS Journal on Computing, INFORMS, vol. 34(6), pages 2968-2988, November.
    2. Lili Pan & Ziyan Luo & Naihua Xiu, 2017. "Restricted Robinson Constraint Qualification and Optimality for Cardinality-Constrained Cone Programming," Journal of Optimization Theory and Applications, Springer, vol. 175(1), pages 104-118, October.
    3. Adrian Gepp & Geoff Harris & Bruce Vanstone, 2020. "Financial applications of semidefinite programming: a review and call for interdisciplinary research," Accounting and Finance, Accounting and Finance Association of Australia and New Zealand, vol. 60(4), pages 3527-3555, December.
    4. De Gennaro Aquino, Luca & Sornette, Didier & Strub, Moris S., 2023. "Portfolio selection with exploration of new investment assets," European Journal of Operational Research, Elsevier, vol. 310(2), pages 773-792.
    5. Mei Choi Chiu & Chi Seng Pun & Hoi Ying Wong, 2017. "Big Data Challenges of High‐Dimensional Continuous‐Time Mean‐Variance Portfolio Selection and a Remedy," Risk Analysis, John Wiley & Sons, vol. 37(8), pages 1532-1549, August.
    6. Zhijun Xu & Jing Zhou, 2023. "A simultaneous diagonalization based SOCP relaxation for portfolio optimization with an orthogonality constraint," Computational Optimization and Applications, Springer, vol. 85(1), pages 247-261, May.
    7. Zhiping Chen & Shen Peng & Abdel Lisser, 2020. "A sparse chance constrained portfolio selection model with multiple constraints," Journal of Global Optimization, Springer, vol. 77(4), pages 825-852, August.
    8. Xiao, Helu & Zhou, Zhongbao & Ren, Teng & Liu, Wenbin, 2022. "Estimation of portfolio efficiency in nonconvex settings: A free disposal hull estimator with non-increasing returns to scale," Omega, Elsevier, vol. 111(C).
    9. Janusz Miroforidis, 2021. "Bounds on efficient outcomes for large-scale cardinality-constrained Markowitz problems," Journal of Global Optimization, Springer, vol. 80(3), pages 617-634, July.
    10. Khodamoradi, T. & Salahi, M. & Najafi, A.R., 2020. "Robust CCMV model with short selling and risk-neutral interest rate," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 547(C).
    11. N. Krejić & E. H. M. Krulikovski & M. Raydan, 2023. "A Low-Cost Alternating Projection Approach for a Continuous Formulation of Convex and Cardinality Constrained Optimization," SN Operations Research Forum, Springer, vol. 4(4), pages 1-24, December.
    12. Xiaojin Zheng & Xiaoling Sun & Duan Li, 2014. "Improving the Performance of MIQP Solvers for Quadratic Programs with Cardinality and Minimum Threshold Constraints: A Semidefinite Program Approach," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 690-703, November.
    13. Steuer, Ralph E. & Qi, Yue & Wimmer, Maximilian, 2024. "Computing cardinality constrained portfolio selection efficient frontiers via closest correlation matrices," European Journal of Operational Research, Elsevier, vol. 313(2), pages 628-636.
    14. Wei Xu & Jie Tang & Ka Fai Cedric Yiu & Jian Wen Peng, 2024. "An Efficient Global Optimal Method for Cardinality Constrained Portfolio Optimization," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 690-704, March.
    15. Tahereh Khodamoradi & Maziar Salahi & Ali Reza Najafi, 2021. "Cardinality-constrained portfolio optimization with short selling and risk-neutral interest rate," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 44(1), pages 197-214, June.
    16. Martin Branda & Max Bucher & Michal Červinka & Alexandra Schwartz, 2018. "Convergence of a Scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization," Computational Optimization and Applications, Springer, vol. 70(2), pages 503-530, June.
    17. Chao Zhang & Zihao Zhang & Mihai Cucuringu & Stefan Zohren, 2021. "A Universal End-to-End Approach to Portfolio Optimization via Deep Learning," Papers 2111.09170, arXiv.org.
    18. Samim Ghamami & Paul Glasserman, 2019. "Submodular Risk Allocation," Management Science, INFORMS, vol. 65(10), pages 4656-4675, October.
    19. Zhou, Zhongbao & Jin, Qianying & Xiao, Helu & Wu, Qian & Liu, Wenbin, 2018. "Estimation of cardinality constrained portfolio efficiency via segmented DEA," Omega, Elsevier, vol. 76(C), pages 28-37.
    20. Vrinda Dhingra & Shiv Kumar Gupta & Amita Sharma, 2023. "Norm constrained minimum variance portfolios with short selling," Computational Management Science, Springer, vol. 20(1), pages 1-35, December.
    21. Juan Francisco Monge, 2017. "Cardinality constrained portfolio selection via factor models," Papers 1708.02424, arXiv.org.
    22. Xiaojin Zheng & Xiaoling Sun & Duan Li & Jie Sun, 2014. "Successive convex approximations to cardinality-constrained convex programs: a piecewise-linear DC approach," Computational Optimization and Applications, Springer, vol. 59(1), pages 379-397, October.
    23. Dimitris Bertsimas & Ryan Cory-Wright, 2022. "A Scalable Algorithm for Sparse Portfolio Selection," INFORMS Journal on Computing, INFORMS, vol. 34(3), pages 1489-1511, May.
    24. Caihua Chen & Xindan Li & Caleb Tolman & Suyang Wang & Yinyu Ye, 2013. "Sparse Portfolio Selection via Quasi-Norm Regularization," Papers 1312.6350, arXiv.org.
    25. Justin A. Sirignano & Gerry Tsoukalas & Kay Giesecke, 2016. "Large-Scale Loan Portfolio Selection," Operations Research, INFORMS, vol. 64(6), pages 1239-1255, December.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Yuanyuan Zhang & Xiang Li & Sini Guo, 2018. "Portfolio selection problems with Markowitz’s mean–variance framework: a review of literature," Fuzzy Optimization and Decision Making, Springer, vol. 17(2), pages 125-158, June.
    2. Eduardo Bered Fernandes Vieira & Tiago Pascoal Filomena, 2020. "Liquidity Constraints for Portfolio Selection Based on Financial Volume," Computational Economics, Springer;Society for Computational Economics, vol. 56(4), pages 1055-1077, December.
    3. Martin Branda & Max Bucher & Michal Červinka & Alexandra Schwartz, 2018. "Convergence of a Scholtes-type regularization method for cardinality-constrained optimization problems with an application in sparse robust portfolio optimization," Computational Optimization and Applications, Springer, vol. 70(2), pages 503-530, June.
    4. Xiaojin Zheng & Xiaoling Sun & Duan Li, 2014. "Improving the Performance of MIQP Solvers for Quadratic Programs with Cardinality and Minimum Threshold Constraints: A Semidefinite Program Approach," INFORMS Journal on Computing, INFORMS, vol. 26(4), pages 690-703, November.
    5. Xiaojin Zheng & Xiaoling Sun & Duan Li & Jie Sun, 2014. "Successive convex approximations to cardinality-constrained convex programs: a piecewise-linear DC approach," Computational Optimization and Applications, Springer, vol. 59(1), pages 379-397, October.
    6. Ruili Sun & Tiefeng Ma & Shuangzhe Liu & Milind Sathye, 2019. "Improved Covariance Matrix Estimation for Portfolio Risk Measurement: A Review," JRFM, MDPI, vol. 12(1), pages 1-34, March.
    7. Jongbin Jung & Seongmoon Kim, 2017. "Developing a dynamic portfolio selection model with a self-adjusted rebalancing method," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(7), pages 766-779, July.
    8. Kolm, Petter N. & Tütüncü, Reha & Fabozzi, Frank J., 2014. "60 Years of portfolio optimization: Practical challenges and current trends," European Journal of Operational Research, Elsevier, vol. 234(2), pages 356-371.
    9. Wei Xu & Jie Tang & Ka Fai Cedric Yiu & Jian Wen Peng, 2024. "An Efficient Global Optimal Method for Cardinality Constrained Portfolio Optimization," INFORMS Journal on Computing, INFORMS, vol. 36(2), pages 690-704, March.
    10. Rossello, Damiano, 2015. "Ranking of investment funds: Acceptability versus robustness," European Journal of Operational Research, Elsevier, vol. 245(3), pages 828-836.
    11. André Alves Portela Santos, 2010. "The Out-of-Sample Performance of Robust Portfolio Optimization," Brazilian Review of Finance, Brazilian Society of Finance, vol. 8(2), pages 141-166.
    12. Woodside-Oriakhi, M. & Lucas, C. & Beasley, J.E., 2011. "Heuristic algorithms for the cardinality constrained efficient frontier," European Journal of Operational Research, Elsevier, vol. 213(3), pages 538-550, September.
    13. Fereshteh Vaezi & Seyed Jafar Sadjadi & Ahmad Makui, 2019. "A portfolio selection model based on the knapsack problem under uncertainty," PLOS ONE, Public Library of Science, vol. 14(5), pages 1-19, May.
    14. Kay Giesecke & Baeho Kim & Jack Kim & Gerry Tsoukalas, 2014. "Optimal Credit Swap Portfolios," Management Science, INFORMS, vol. 60(9), pages 2291-2307, September.
    15. Yuki Shigeta, 2016. "Optimality of Naive Investment Strategies in Dynamic MeanVariance Optimization Problems with Multiple Priors," Discussion papers e-16-004, Graduate School of Economics , Kyoto University.
    16. Tahereh Khodamoradi & Maziar Salahi & Ali Reza Najafi, 2021. "Cardinality-constrained portfolio optimization with short selling and risk-neutral interest rate," Decisions in Economics and Finance, Springer;Associazione per la Matematica, vol. 44(1), pages 197-214, June.
    17. Mansini, Renata & Ogryczak, Wlodzimierz & Speranza, M. Grazia, 2014. "Twenty years of linear programming based portfolio optimization," European Journal of Operational Research, Elsevier, vol. 234(2), pages 518-535.
    18. Plachel, Lukas, 2019. "A unified model for regularized and robust portfolio optimization," Journal of Economic Dynamics and Control, Elsevier, vol. 109(C).
    19. DeMiguel, Victor & Martin-Utrera, Alberto & Nogales, Francisco J., 2013. "Size matters: Optimal calibration of shrinkage estimators for portfolio selection," Journal of Banking & Finance, Elsevier, vol. 37(8), pages 3018-3034.
    20. Khodamoradi, T. & Salahi, M. & Najafi, A.R., 2020. "Robust CCMV model with short selling and risk-neutral interest rate," Physica A: Statistical Mechanics and its Applications, Elsevier, vol. 547(C).

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:inm:oropre:v:61:y:2013:i:3:p:745-761. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.