IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v53y2012i3p681-709.html
   My bibliography  Save this article

A local relaxation method for the cardinality constrained portfolio optimization problem

Author

Listed:
  • Walter Murray
  • Howard Shek

Abstract

The NP-hard nature of cardinality constrained mean-variance portfolio optimization problems has led to a number of different algorithms with varying degrees of success in reaching optimality given limited computational resources and under the presence of strict time constraints present in practice. The proposed local relaxation algorithm explores the inherent structure of the objective function. It solves a sequence of small, local, quadratic-programs by first projecting asset returns onto a reduced metric space, followed by clustering in this space to identify sub-groups of assets that best accentuate a suitable measure of similarity amongst different assets. The algorithm can either be cold started using a suitable heuristic method such as the centroids of initial clusters or be warm started based on the last output. Results, using a basket of up to 3,000 stocks and with different cardinality constraints, indicates that the proposed algorithm can lead to significant performance gain over popular branch-and-cut methods. One key application of this algorithm is in dealing with large scale cardinality constrained portfolio optimization under tight time constraint, such as for the purpose of index tracking or index arbitrage at high frequency. Copyright Springer Science+Business Media, LLC 2012

Suggested Citation

  • Walter Murray & Howard Shek, 2012. "A local relaxation method for the cardinality constrained portfolio optimization problem," Computational Optimization and Applications, Springer, vol. 53(3), pages 681-709, December.
    • Handle: RePEc:spr:coopap:v:53:y:2012:i:3:p:681-709
    DOI: 10.1007/s10589-012-9471-1
    as

    Download full text from publisher

    File URL: http://hdl.handle.net/10.1007/s10589-012-9471-1
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1007/s10589-012-9471-1?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Harry Markowitz, 1952. "Portfolio Selection," Journal of Finance, American Finance Association, vol. 7(1), pages 77-91, March.
    2. Andre F. Perold, 1984. "Large-Scale Portfolio Optimization," Management Science, INFORMS, vol. 30(10), pages 1143-1160, October.
    3. Hiroshi Konno & Rei Yamamoto, 2005. "Integer programming approaches in mean-risk models," Computational Management Science, Springer, vol. 4(4), pages 339-351, November.
    4. Yitzhaki, Shlomo, 1982. "Stochastic Dominance, Mean Variance, and Gini's Mean Difference," American Economic Review, American Economic Association, vol. 72(1), pages 178-185, March.
    5. Hiroshi Konno & Hiroaki Yamazaki, 1991. "Mean-Absolute Deviation Portfolio Optimization Model and Its Applications to Tokyo Stock Market," Management Science, INFORMS, vol. 37(5), pages 519-531, May.
    6. Peter Reinhard Hansen & Zhuo Huang & Howard Howan Shek, 2012. "Realized GARCH: a joint model for returns and realized measures of volatility," Journal of Applied Econometrics, John Wiley & Sons, Ltd., vol. 27(6), pages 877-906, September.
    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. Chen, Qi-an & Hu, Qingyu & Yang, Hu & Qi, Kai, 2022. "A kind of new time-weighted nonnegative lasso index-tracking model and its application," The North American Journal of Economics and Finance, Elsevier, vol. 59(C).
    2. 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.
    3. Jize Zhang & Tim Leung & Aleksandr Aravkin, 2018. "A Relaxed Optimization Approach for Cardinality-Constrained Portfolio Optimization," Papers 1810.10563, arXiv.org.
    4. Max Bucher & Alexandra Schwartz, 2018. "Second-Order Optimality Conditions and Improved Convergence Results for Regularization Methods for Cardinality-Constrained Optimization Problems," Journal of Optimization Theory and Applications, Springer, vol. 178(2), pages 383-410, August.
    5. Nasim Dehghan Hardoroudi & Abolfazl Keshvari & Markku Kallio & Pekka Korhonen, 2017. "Solving cardinality constrained mean-variance portfolio problems via MILP," Annals of Operations Research, Springer, vol. 254(1), pages 47-59, July.
    6. Leonardo Riegel Sant’Anna & Tiago Pascoal Filomena & Pablo Cristini Guedes & Denis Borenstein, 2017. "Index tracking with controlled number of assets using a hybrid heuristic combining genetic algorithm and non-linear programming," Annals of Operations Research, Springer, vol. 258(2), pages 849-867, November.
    7. Madani Bezoui & Mustapha Moulaï & Ahcène Bounceur & Reinhardt Euler, 2019. "An iterative method for solving a bi-objective constrained portfolio optimization problem," Computational Optimization and Applications, Springer, vol. 72(2), pages 479-498, March.
    8. Christian Kanzow & Andreas B. Raharja & Alexandra Schwartz, 2021. "Sequential optimality conditions for cardinality-constrained optimization problems with applications," Computational Optimization and Applications, Springer, vol. 80(1), pages 185-211, September.
    9. Alexander Nikiporenko, 2023. "Time-limited Metaheuristics for Cardinality-constrained Portfolio Optimisation," Papers 2307.04045, arXiv.org.

    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. Panos Xidonas & George Mavrotas, 2014. "Comparative issues between linear and non-linear risk measures for non-convex portfolio optimization: evidence from the S&P 500," Quantitative Finance, Taylor & Francis Journals, vol. 14(7), pages 1229-1242, July.
    2. Ogryczak, Wlodzimierz & Ruszczynski, Andrzej, 1999. "From stochastic dominance to mean-risk models: Semideviations as risk measures," European Journal of Operational Research, Elsevier, vol. 116(1), pages 33-50, July.
    3. Francesco Cesarone & Andrea Scozzari & Fabio Tardella, 2015. "Linear vs. quadratic portfolio selection models with hard real-world constraints," Computational Management Science, Springer, vol. 12(3), pages 345-370, July.
    4. Massol, Olivier & Banal-Estañol, Albert, 2014. "Export diversification through resource-based industrialization: The case of natural gas," European Journal of Operational Research, Elsevier, vol. 237(3), pages 1067-1082.
    5. Akhter Mohiuddin Rather & V. N. Sastry & Arun Agarwal, 2017. "Stock market prediction and Portfolio selection models: a survey," OPSEARCH, Springer;Operational Research Society of India, vol. 54(3), pages 558-579, September.
    6. Massimiliano Caporin & Grégory M. Jannin & Francesco Lisi & Bertrand B. Maillet, 2014. "A Survey On The Four Families Of Performance Measures," Journal of Economic Surveys, Wiley Blackwell, vol. 28(5), pages 917-942, December.
    7. Benati, Stefano, 2003. "The optimal portfolio problem with coherent risk measure constraints," European Journal of Operational Research, Elsevier, vol. 150(3), pages 572-584, November.
    8. Paolo Laureti & Matus Medo & Yi-Cheng Zhang, 2010. "Analysis of Kelly-optimal portfolios," Quantitative Finance, Taylor & Francis Journals, vol. 10(7), pages 689-697.
    9. Philipp Baumann & Norbert Trautmann, 2013. "Portfolio-optimization models for small investors," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 77(3), pages 345-356, June.
    10. Leung, Pui-Lam & Ng, Hon-Yip & Wong, Wing-Keung, 2012. "An improved estimation to make Markowitz’s portfolio optimization theory users friendly and estimation accurate with application on the US stock market investment," European Journal of Operational Research, Elsevier, vol. 222(1), pages 85-95.
    11. X Cai & K L Teo & X Q Yang & X Y Zhou, 2004. "Minimax portfolio optimization: empirical numerical study," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 55(1), pages 65-72, January.
    12. 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.
    13. Hautsch, Nikolaus & Voigt, Stefan, 2017. "Large-Scale Portfolio Allocation Under Transaction Costs and Model Uncertainty: Adaptive Mixing of High- and Low-Frequency Information," VfS Annual Conference 2017 (Vienna): Alternative Structures for Money and Banking 168222, Verein für Socialpolitik / German Economic Association.
    14. H S Ryoo, 2007. "A compact mean-variance-skewness model for large-scale portfolio optimization and its application to the NYSE market," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 58(4), pages 505-515, April.
    15. Jun-ya Gotoh & Hiroshi Konno, 2000. "Third Degree Stochastic Dominance and Mean-Risk Analysis," Management Science, INFORMS, vol. 46(2), pages 289-301, February.
    16. Branda, Martin, 2013. "Diversification-consistent data envelopment analysis with general deviation measures," European Journal of Operational Research, Elsevier, vol. 226(3), pages 626-635.
    17. Fang, Yong & Chen, Lihua & Fukushima, Masao, 2008. "A mixed R&D projects and securities portfolio selection model," European Journal of Operational Research, Elsevier, vol. 185(2), pages 700-715, March.
    18. Schuhmacher, Frank & Auer, Benjamin R., 2014. "Sufficient conditions under which SSD- and MR-efficient sets are identical," European Journal of Operational Research, Elsevier, vol. 239(3), pages 756-763.
    19. Arenas Parra, M. & Bilbao Terol, A. & Rodriguez Uria, M. V., 2001. "A fuzzy goal programming approach to portfolio selection," European Journal of Operational Research, Elsevier, vol. 133(2), pages 287-297, January.
    20. Polak, George G. & Rogers, David F. & Sweeney, Dennis J., 2010. "Risk management strategies via minimax portfolio optimization," European Journal of Operational Research, Elsevier, vol. 207(1), pages 409-419, November.

    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:spr:coopap:v:53:y:2012:i:3:p:681-709. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.