Heuristic algorithms for the cardinality constrained efficient frontier. (English) Zbl 1218.91151
Summary: This paper examines the application of genetic algorithm, tabu search and simulated annealing metaheuristic approaches to finding the cardinality constrained efficient frontier that arises in financial portfolio optimisation. We consider the mean-variance model of Markowitz as extended to include the discrete restrictions of buy-in thresholds and cardinality constraints. Computational results are reported for publicly available data sets drawn from seven major market indices involving up to 1318 assets. Our results are compared with previous results given in the literature illustrating the effectiveness of the proposed metaheuristics in terms of solution quality and computation time.
MSC:
| 91G10 | Portfolio theory |
| 91G60 | Numerical methods (including Monte Carlo methods) |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
efficient frontier; genetic algorithm; portfolio optimisation; simulated annealing; tabu searchReferences:
| [1] | (Aarts, E. H.L.; Lenstra, J. K., Local Search in Combinatorial Optimization (2003), Princeton University Press: Princeton University Press Princeton, USA) · Zbl 1106.90002 |
| [2] | Alander, J. T., On optimal population size of genetic algorithms, (Computer Systems and Software Engineering - CompEuro 1992 Proceedings (1992), IEEE Computer Society Press), 65-70 |
| [3] | Anagnostopoulos, K. P.; Mamanis, G., A portfolio optimization model with three objectives and discrete variables, Computers & Operations Research, 37, 1285-1297 (2010) · Zbl 1178.90299 |
| [4] | Beasley, J. E., OR-Library: Distributing test problems by electronic mail, Journal of the Operational Research Society, 41, 1069-1072 (1990) |
| [5] | Beasley, J. E., Population heuristics, (Pardalos, P. M.; Resende, M. G.C., Handbook of Applied Optimization (2002), Oxford University Press: Oxford University Press Oxford), 138-157 · Zbl 0996.90001 |
| [6] | Bertsimas, D.; Shioda, R., Algorithm for cardinality-constrained quadratic optimization, Computational Optimization and Applications, 43, 1-22 (2009) · Zbl 1178.90262 |
| [7] | Bienstock, D., Computational study of a family of mixed-integer quadratic programming problems, Mathematical Programming, 74, 121-140 (1996) · Zbl 0855.90090 |
| [8] | Bonami, P.; Lejeune, M. A., An exact solution approach for portfolio optimization problems under stochastic and integer constraints, Operations Research, 57, 650-670 (2009) · Zbl 1226.90049 |
| [9] | Branke, J.; Scheckenbach, B.; Stein, M.; Deb, K.; Schmeck, H., Portfolio optimization with an envelope-based multi-objective evolutionary algorithm, European Journal of Operational Research, 199, 684-693 (2009) · Zbl 1176.90527 |
| [10] | (Burke, E. K.; Kendall, G., Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques (2005), Springer) · Zbl 1140.90015 |
| [11] | Cerny, V., Thermodynamical approach to the travelling salesman problem: An efficient simulation algorithm, Journal of Optimization Theory and Applications, 45, 41-51 (1985) · Zbl 0534.90091 |
| [12] | Chang, T.-J.; Meade, N.; Beasley, J. E.; Sharaiha, Y. M., Heuristics for cardinality constrained portfolio optimisation, Computers & Operations Research, 27, 1271-1302 (2000) · Zbl 1032.91074 |
| [13] | Chang, T.-J.; Yang, S.-C.; Chang, K.-J., Portfolio optimization problems in different risk measures using genetic algorithm, Expert Systems with Applications, 36, 10529-10537 (2009) |
| [14] | Chiam, S. C.; Tan, K. C.; Al Mamum, A., Evolutionary multi-objective portfolio optimization in practical context, International Journal of Automation and Computing, 5, 67-80 (2008) |
| [15] | Corazza, M.; Favaretto, D., On the existence of solutions to the quadratic mixed-integer mean-variance portfolio selection problem, European Journal of Operational Research, 176, 1947-1960 (2007) · Zbl 1109.90061 |
| [16] | Crama, Y.; Schyns, M., Simulated annealing for complex portfolio selection problems, European Journal of Operational Research, 150, 546-571 (2003) · Zbl 1046.91057 |
| [17] | Cura, T., Particle swarm optimization approach to portfolio optimization, Nonlinear Analysis: Real World Applications, 10, 2396-2406 (2009) · Zbl 1163.90669 |
| [18] | Derigs, U.; Nickel, N.-H., Meta-heuristic based decision support for portfolio optimisation with a case study on tracking error minimization in passive portfolio management, OR Spectrum, 25, 345-378 (2003) · Zbl 1043.91028 |
| [19] | Derigs, U.; Nickel, N.-H., On a local-search heuristic for a class of tracking error minimization problems in portfolio management, Annals of Operation Research, 131, 45-77 (2004) · Zbl 1067.91026 |
| [20] | Dongarra, J.J., 2009. Performance of Various Computers Using Standard Linear Equations Software, Report CS-89-85. University of Tennessee, USA. Available from: <http://www.netlib.org/benchmark/performance.ps>; Dongarra, J.J., 2009. Performance of Various Computers Using Standard Linear Equations Software, Report CS-89-85. University of Tennessee, USA. Available from: <http://www.netlib.org/benchmark/performance.ps> |
| [21] | Duran, F. C.; Cotta, C.; Fernandez, A. J., Evolutionary optimization for multiobjective portfolio selection under Markowitz’s model with application to the Caracas stock exchange, (Chiong, R., Nature-Inspired Algorithms for Optimisation: Studies in Computational Intelligence, vol. 193 (2009), Springer: Springer Berlin/Heidelberg), 489-509 |
| [22] | Ehrgott, M.; Klamroth, K.; Schwehm, C., An MCDM approach to portfolio optimization, European Journal of Operational Research, 155, 752-770 (2004) · Zbl 1043.91016 |
| [23] | Ellison, E.F.D., Hajian, M., Levkovitz, K., Maros, I., Mitra, G., 1999. A Fortran Based Mathematical Programming System. FortMP, Brunel University, UK; NAG Ltd., Oxford, UK.; Ellison, E.F.D., Hajian, M., Levkovitz, K., Maros, I., Mitra, G., 1999. A Fortran Based Mathematical Programming System. FortMP, Brunel University, UK; NAG Ltd., Oxford, UK. |
| [24] | Fernandez, A.; Gomez, S., Portfolio selection using neural networks, Computers & Operations Research, 34, 1177-1191 (2007) · Zbl 1102.91322 |
| [25] | Fourer, F.; Gay, D. M.; Kernighan, B. W., AMPL: A Modeling Language for Mathematical Programming (2002), Brooks/Cole Publishing Company/Cengage Learning |
| [26] | Gendreau, M., An introduction to tabu search, (Glover, F.; Kochenberger, G. A., Handbook of Metaheuristics (2003), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, The Netherlands), 37-54 · Zbl 1102.90380 |
| [27] | Glover, F., Future paths for integer programming and links to artificial intelligence, Computers & Operations Research, 13, 533-549 (1986) · Zbl 0615.90083 |
| [28] | Glover, F.; Laguna, M., Tabu search, (Reeves, C. R., Modern Heuristic Techniques for Combinatorial Problems (1993), Blackwell Scientific Publications: Blackwell Scientific Publications Oxford, UK), 70-150 · Zbl 0942.90500 |
| [29] | Glover, F.; Laguna, M., Tabu Search (1997), Kluwer Academic Publishers: Kluwer Academic Publishers Dordrecht, The Netherlands · Zbl 0930.90083 |
| [30] | Gulpinar, N.; An, L. T.H.; Moeini, M., Robust investment strategies with discrete asset choice constraints using DC programming, Optimization, 59, 45-62 (2010) · Zbl 1188.90184 |
| [31] | Hillier, F. S.; Lieberman, G. J., Introduction to Operations Research (2010), McGraw-Hill · Zbl 0155.28202 |
| [32] | Holland, J. H., Adaptation in Natural and Artificial Systems: An Introductory Analysis With Applications to Biology, Control, and Artificial Intelligence (1975), University of Michigan Press: University of Michigan Press Ann Arbor, MI, USA · Zbl 0317.68006 |
| [33] | Jobst, N. J.; Horniman, M. D.; Lucas, C. A.; Mitra, G., Computational aspects of alternative portfolio selection models in the presence of discrete asset choice constraints, Quantitative Finance, 1, 489-501 (2001) · Zbl 1405.91559 |
| [34] | Kellerer, H.; Mansini, R.; Speranza, M. G., On selecting portfolios with fixed costs and minimum transaction lots, Annals of Operations Research, 99, 287-304 (2000) · Zbl 1059.91042 |
| [35] | Kirkpatrick, S.; Gelatt, C. D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 671-680 (1983) · Zbl 1225.90162 |
| [36] | (Larranaga, P.; Lozano, J. A., Estimation of Distribution Algorithms: A New Tool For Evolutionary Computation (2001), Springer) · Zbl 0979.00024 |
| [37] | Lemke, C. E.; Howson, J. T., Equilibrium points of bimatrix games, Journal of the Society for Industrial and Applied Mathematics, 12, 413-423 (1964) · Zbl 0128.14804 |
| [38] | Li, D.; Sun, X.; Wang, J., Optimal lot solution to cardinality constrained mean-variance formulation for portfolio selection, Mathematical Finance, 16, 83-101 (2006) · Zbl 1128.91028 |
| [39] | Mansini, R.; Speranza, M. G., Heuristic algorithms for the portfolio selection problem with minimum transaction lots, European Journal of Operational Research, 114, 219-233 (1999) · Zbl 0935.91022 |
| [40] | Maringer, D.; Kellerer, H., Optimization of cardinality constrained portfolios with a hybrid local search algorithm, OR Spectrum, 25, 481-495 (2003) · Zbl 1031.91054 |
| [41] | Markowitz, H., Portfolio selection, Journal of Finance, 7, 77-91 (1952) |
| [42] | Markowitz, H. M., The optimization of a quadratic function subject to linear constraints, Naval Research Logistics Quarterly, 3, 111-133 (1956) |
| [43] | Mitchell, M., An Introduction to Genetic Algorithms (1996), MIT Press: MIT Press Cambridge, MA, USA |
| [44] | Moral-Escudero, R., Ruiz-Torrubiano, R., Suarez, A., 2006. Selection of optimal investment portfolios with cardinality constraints. In: Proceedings of the 2006 IEEE Congress on Evolutionary Computation, pp. 2382-2388.; Moral-Escudero, R., Ruiz-Torrubiano, R., Suarez, A., 2006. Selection of optimal investment portfolios with cardinality constraints. In: Proceedings of the 2006 IEEE Congress on Evolutionary Computation, pp. 2382-2388. |
| [45] | Pai, G. A.V.; Michel, T., Evolutionary optimization of constrained \(k\)-means clustered assets for diversification in small portfolios, IEEE Transactions on Evolutionary Computation, 13, 1030-1053 (2009) |
| [46] | Ruiz-Torrubiano, R.; Suarez, A., Hybrid approaches and dimensionality reduction for portfolio selection with cardinality constraints, IEEE Computational Intelligence Magazine, 5, 2, 92-107 (2010) |
| [47] | Schaerf, A., Local search techniques for constrained portfolio selection problems, Computational Economics, 20, 177-190 (2002) · Zbl 1036.91026 |
| [48] | Shaw, D. X.; Liu, S.; Kopman, L., Lagrangian relaxation procedure for cardinality-constrained portfolio optimization, Optimization Methods & Software, 23, 411-420 (2008) · Zbl 1162.90531 |
| [49] | Soleimani, H.; Golmakani, H. R.; Salimi, M. H., Markowitz-based portfolio selection with minimum transaction lots, cardinality constraints and regarding sector capitalization using genetic algorithm, Expert Systems with Applications, 36, 5058-5063 (2009) |
| [50] | Streichert, F., Tanaka-Yamawaki, M., 2006. The effect of local search on the constrained portfolio selection problem. In: Proceedings of the 2006 IEEE Congress on Evolutionary Computation, pp. 2368-2374.; Streichert, F., Tanaka-Yamawaki, M., 2006. The effect of local search on the constrained portfolio selection problem. In: Proceedings of the 2006 IEEE Congress on Evolutionary Computation, pp. 2368-2374. |
| [51] | Syam, S. S., A dual ascent method for the portfolio selection problem with multiple constraints and linked proposals, European Journal of Operational Research, 108, 196-207 (1998) · Zbl 0952.91035 |
| [52] | Vielma, J. P.; Ahmed, S.; Nemhauser, G. L., A lifted linear programming branch-and-bound algorithm for mixed-integer conic quadratic programs, INFORMS Journal on Computing, 20, 438-450 (2008) · Zbl 1243.90170 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
