Abstract
Several portfolio selection models take into account practical limitations on the number of assets to include and on their weights in the portfolio. We present here a study of the Limited Asset Markowitz (LAM) model, where the assets are limited with the introduction of quantity and cardinality constraints.
We propose a completely new approach for solving the LAM model based on a reformulation as a Standard Quadratic Program, on a new lower bound that we establish, and on other recent theoretical and computational results for such problem. These results lead to an exact algorithm for solving the LAM model for small size problems. For larger problems, such algorithm can be relaxed to an efficient and accurate heuristic procedure that is able to find the optimal or the best-known solutions for problems based on some standard financial data sets that are used by several other authors. We also test our method on five new data sets involving real-world capital market indices from major stock markets. We compare our results with those of CPLEX and with those obtained with very recent heuristic approaches in order to illustrate the effectiveness of our method in terms of solution quality and of computation time. All our data sets and results are publicly available for use by other researchers.
Similar content being viewed by others
References
Anagnostopoulos, K. P., & Mamanis, G. (2010). A portfolio optimization model with three objectives and discrete variables. Computers & Operations Research, 37, 1285–1297.
Anagnostopoulos, K. P., & Mamanis, G. (2011). The mean-variance cardinality constrained portfolio optimization problem: an experimental evaluation of five multiobjective evolutionary algorithms. Expert Systems with Applications, 38, 14208–14217.
Armañanzas, R., & Lozano, J. A. (2005). A multiobjective approach to the portfolio optimization problem. In Proceedings of the 2005 IEEE congress on evolutionary computation (CEC 2005) (Vol. 2, pp. 1388–1395). New York: IEEE Press. doi:10.1109/CEC.2005.1554852.
Beasley, J. E. (1990). Or-library: distributing test problems by electronic mail. Journal of the Operational Research Society, 41, 1069–1072.
Bertsimas, D., & Shioda, R. (2009). Algorithms for cardinality-constrained quadratic optimization. Computational Optimization and Applications, 43, 1–22.
Bienstock, D. (1996). Computational study of a family of mixed-integer quadratic programming problems. Mathematical Programming, 74, 121–140.
Bomze, I. M. (1998). On standard quadratic optimization problems. Journal of Global Optimization, 13, 369–387.
Bomze, I. M., Locatelli, M., & Tardella, F. (2008). New and old bounds for standard quadratic optimization: dominance, equivalence and incomparability. Mathematical Programming, 115, 31–64.
Borchers, B., & Mitchell, J. E. (1994). An improved branch and bound algorithm for mixed integer nonlinear programs. Computers & Operations Research, 21, 359–367.
Branke, J., Scheckenbach, B., Stein, M., Deb, K., & Schmeck, H. (2009). Portfolio optimization with an envelope-based multi-objective evolutionary algorithm. European Journal of Operational Research, 199, 684–693.
Canakgoz, N. A., & Beasley, J. E. (2008). Mixed-integer programming approaches for index tracking and enhanced indexation. European Journal of Operational Research, 196, 384–399.
Cesarone, F., Scozzari, A., & Tardella, F. (2008). Efficient algorithms for mean-variance portfolio optimization with hard real-world constraints. In Proceedings of the 18th AFIR colloquium: financial risk in a changing world, Rome.
Chang, T.-J., Meade, M., Beasley, J. E., & Sharaiha, Y. M. (2000). Heuristics for cardinality constrained portfolio optimization. Computers & Operations Research, 27, 1271–1302.
Chiam, S. C., Tan, K. C., & Al Mamum, A. (2008). Evolutionary multi-objective portfolio optimization in practical context. International Journal of Automation and Computing, 5, 67–80.
Crama, Y., & Schyns, M. (2003). Simulated annealing for complex portfolio selection problems. European Journal of Operational Research, 150, 546–571.
Di Gaspero, L., Di Tollo, G., Roli, A., & Schaerf, A. (2007). Hybrid local search for constrained financial portfolio selection problems. In P. Van Hentenryck & L. Wolsey (Eds.), Lecture notes in computer science: Vol. 4510. Integration of AI and OR techniques in constraint programming for combinatorial optimization problems, fourth international conference, CPAIOR 2007 (pp. 44–58). Berlin: Springer.
Di Gaspero, L., Di Tollo, G., Roli, A., & Schaerf, A. (2010). Hybrid metaheuristics for constrained portfolio selection problems. Quantitative Finance. doi:10.1080/14697680903460168.
Ehrgott, M., Klamroth, K., & Schwehm, C. (2004). An MCDM approach to portfolio optimization. European Journal of Operational Research, 155, 752–770.
Elton, E. J., & Gruber, M. J. (1995). Modern portfolio theory and investment analysis (5th ed.). New York: Wiley.
Fernández, A., & Gómez, S. (2007). Portfolio selection using neural networks. Computers & Operations Research, 34, 1177–1191.
Fiacco, A. V., & Kyparisis, J. (1986). Convexity and concavity properties of the optimal value function in parametric nonlinear programming. Journal of Optimization Theory and Applications, 48, 95–126.
Fieldsend, J. E., Matatko, J., & Peng, M. (2004). Cardinality constrained portfolio optimisation. In Lecture notes in computer science (Vol. 3177, pp. 788–793).
Frangioni, A., & Gentile, C. (2006). Perspective cuts for a class of convex 0–1 mixed integer programs. Mathematical Programming, 106, 225–236.
Gomez, M. A., Flores, C. X., & Osorio, M. A. (2006). Hybrid search for cardinality constrained portfolio optimization. In Proceedings of the 8th annual conference on genetic and evolutionary computation (pp. 1865–1866). New York: ACM.
Gulpinar, N., An, L. T. H., & Moeini, M. (2010). Robust investment strategies with discrete asset choice constraints using DC programming. Optimization, 59, 46–62.
Holmstrom, K., Goran, A. O., & Edvall, M. M. (2007). Users guide for TOMLAB.
Jobst, N. J., Horniman, M. D., Lucas, C. A., & Mitra, G. (2001). Computational aspects of alternative portfolio selection models in the presence of discrete asset choice constraints. Quantitative Finance, 1, 489–501.
King, A. J. (1993). Asymmetric risk measures and tracking models for portfolio optimization under uncertainty. Annals of Operations Research, 45, 165–177.
Konno, H., & Yamazaki, H. (1991). Mean-absolute deviation portfolio optimization model and its application to Tokyo stock exchange. Management Science, 37, 519–531.
Lee, E. K., & Mitchell, J. E. (1997). Computational experience of an interior-point SQP algorithm in a parallel branch-and-bound framework. In Proceedings of high performance optimization technique. Berlin: Springer.
Lemke, C. E., & Howson, J. T. (1964). Equilibrium points of bimatrix games. Journal of the Society for Industrial and Applied Mathematics, 12, 414–423.
Li, D., Sun, X., & Wang, J. (2006). Optimal lot solution to cardinality constrained mean-variance formulation for portfolio selection. Mathematical Finance, 16, 83–101.
Maringer, D., & Kellerer, H. (2003). Optimization of cardinality constrained portfolios with a hybrid local search algorithm. OR-Spektrum, 25, 481–495.
Markowitz, H. M. (1952). Portfolio selection. Journal of Finance, 7, 77–91.
Markowitz, H. M. (1959). Cowles foundation for research in economics at Yale university, monograph: Vol. 16. Portfolio selection: efficient diversification of investments. New York: Wiley.
Markowitz, H. M. (1987). Mean-variance analysis in portfolio choice and capital markets. Oxford: Basil Blackwell.
Martinjak, I. (2009). Cardinality constrained portfolio optimization by means of genetic algorithms. In Proceedings of the 20th central European conference on information and intelligent systems, Varazin, Croatia.
Mills, T. C. (1997). Stylized facts on the temporal and distributional properties of daily FT-SE returns. Applied Financial Economics, 7, 599–604.
Mitra, G., Kriakis, T., Lucas, C., & Pirbhai, M. (2003). Advances in portfolio construction and implementation. In S. E. Stachell & A. Scowcroft (Eds.), A review of portfolio planning: models and systems. Oxford: Butterworth-Heinemann.
Moral-Escudero, R., Ruiz-Torrubiano, R., & Suárez, A. (2006). Selection of optimal investment with cardinality constraints. In Proceedings of the IEEE world congress on evolutionary computation, CEC 2006 (pp. 2382–2388). New York: IEEE Press.
Morgan, J. P. (1996). Riskmetrics-technical document (Tech. report, 4th ed.). New York: Morgan Guaranty Trust Company of New York.
Rockafellar, R. T., & Uryasev, S. (2000). Optimization of conditional value-at-risk. Journal of Risk, 2, 21–42.
Ruiz-Torrubiano, R., & Suarez, A. (2010). Hybrid approaches and dimensionality reduction for portfolio selection with cardinality constrains. IEEE Computational Intelligence Magazine, 5, 92–107.
Schaerf, A. (2002). Local search techniques for constrained portfolio selection problems. Computational Economics, 20, 177–190.
Scozzari, A., & Tardella, F. (2008). A clique algorithm for standard quadratic programming. Discrete Applied Mathematics, 156, 2439–2448.
Shaw, D. X., Liu, S., & Kopman, L. (2008). Lagrangian relaxation procedure for cardinality-constrained portfolio optimization. Optimization Methods & Software, 23, 411–420.
Streichert, F., & Tanaka-Yamawaki, M. (2006). The effect of local search on the constrained portfolio selection problem. In IEEE international congress on evolutionary computing, proceedings, CEC (pp. 2368–2374). New York: ACM.
Streichert, F., Ulmer, H., & Zell, A. (2003). Evolutionary algorithms and the cardinality constrained portfolio selection problem. In D. Ahr, R. Fahrion, M. Oswald & G. Reinelt (Eds.), Selected papers of the international conference on operations research. Berlin: Springer.
Streichert, F., Ulmer, H., & Zell, A. (2004). Comparing discrete and continuous genotypes on the constrained portfolio selection problem. In Genetic and evolutionary computation conference, proceedings, Part II, GECCO (pp. 1239–1250). Berlin: Springer.
Tardella, F. (2004). Connections between continuous and combinatorial optimization problems through an extension of the fundamental theorem of linear programming. Electronic Notes in Discrete Mathematics, 17, 257–262.
Tardella, F. (2011). The fundamental theorem of linear programming: extensions and application. Optimization, 60, 283–301.
Vielma, J. P., Ahmed, S., & Nemhauser, G. L. (2008). A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs. INFORMS Journal on Computing, 20, 438–450.
Woodside-Oriakhi, M., Lucas, C., & Beasley, J. E. (2011). Heuristic algorithms for the cardinality constrained efficient frontier. European Journal of Operational Research, 213, 538–550.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Cesarone, F., Scozzari, A. & Tardella, F. A new method for mean-variance portfolio optimization with cardinality constraints. Ann Oper Res 205, 213–234 (2013). https://doi.org/10.1007/s10479-012-1165-7
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-012-1165-7