Empirical analysis of algorithms for solving the index tracking problem

A. R. Faizliev ; A. A. Khomchenko ; S. P. Sidorov

Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, Tome 18 (2018) no. 1, pp. 101-124.

Résumé

Index tracking is a passive financial strategy that tries to replicate the performance of a given index or benchmark. The aim of investor is to find the weights of assets in her/his portfolio that minimize the tracking error, i.e. difference between the performance of the index and the portfolio. The paper considers the index tracking problem with cardinality constraint, i.e. the limit on the number of assets in the portfolio with non-zero weights. Index tracking problem with cardinality constraint is NP-hard problem and it usually requires the development of heuristic algorithms such as genetic algorithms and differential evolution algorithm. In this paper we will examine different algorithms for solving the problem in $l_2$-norm, including greedy algorithm, differential evolution algorithm and LASSO-type algorithm. In our empirical analysis we use publicly available data relating to three major market indices (the Hang Seng (Hong Kong), S 100 (USA) and the Nikkei 225 (Japan). To compare the three approaches (the greedy and the LASSO-type algorithms, the greedy and the differential evolution algorithms) to the index tracking problem, we use both a moving time window procedure and stochastic dominance principle. Moreover, we carried out the comparison using both for in-sample and out-of-sample tracking error analysis.

Bibliographie

[1] Markowits H. M., “Portfolio Selection”, J. Finance, 7:1 (1952), 71–91 | DOI | MR

[2] Roll R., “A mean/variance analysis of tracking error”, J. Portfol. Mgmt., 18:4 (1992), 13–22 | DOI

[3] Takeda A., Niranjan M., Gotoh J., Kawahara Y., “Simultaneous pursuit of out-of-sample performance and sparsity in index tracking portfolios”, Comput. Manag. Sci., 10:1 (2013), 21–49 | DOI | MR

[4] Brodie J., Daubechiesa I., De Molc C., Giannoned D., Lorisc I., “Sparse and stable Markowitz portfolios”, PNAS, 106:30 (2009), 12267–12272 | DOI

[5] Gilli M., Kellezi E., “The threshold accepting heuristic for index tracking”, Financial Engineering, E-Commerce and Supply Chain, 2002, 1–18 | DOI

[6] Prigent J.-L., Portfolio Optimization and Performance Analysis, Chapman Hall/CRC, Boca Raton, 2007, 456 pp. | MR

[7] Rudolf M., Wolter H. J., Zimmermann H., “A linear model for tracking error minimization”, J. Banking Finance, 23:1 (1999), 85–103 | DOI

[8] DeMiguel V., Garlappi L., Uppal R., Optimal Versus Naive Diversification: How Inefficient is the 1/N Portfolio Strategy?, Rev. Financ. Stud., 22:5 (2009), 1915–1953 | DOI | MR

[9] Bertero M., Boccacci P., Introduction to Inverse Problems in Imaging, Institute of Physics Publ., L., 1998, 352 pp. | DOI | MR

[10] Chen S. S., Donoho D. L., Saunders M. A., “Atomic Decomposition by Basis Pursuit”, SIAM Review, 43:1 (2001), 129–159 | DOI | MR

[11] Daubechies I., Defrise M., De Mol C., “An Iterative Thresholding Algorithm for Linear Inverse Problems With a Sparsity Constraint”, Communications on Pure and Appl. Math., 57:11 (2004), 1413–1457 | DOI | MR

[12] Osborne M. R., Presnell B., Turlach B. A., “A New Approach to Variable Selection in Least Squares Problems”, IMA J. Numer. Anal., 20:3 (2000), 389–403 | DOI | MR

[13] Osborne M. R., Presnell B., Turlach B. A., “On the LASSO and Its Dual”, J. Comput. and Graphical Statistics, 9:2 (2004), 319–337 | DOI | MR

[14] Efron B., Hastie T., Johnstone I., Tibshirani R., “Least Angle Regression”, Ann. Statist., 32:2 (2004), 407–499 | DOI | MR

[15] Zhang T., “Adaptive forward-backward greedy algorithm for sparse learning with linear models”, Advances in Neural Information Processing Systems 21, NIPS 2008, Curran Associates, Inc., 2008, 1921–1928

[16] Tikhonov A. N., “Incorrect problems of linear algebra and a stable method for their solution”, Sov. Math. Dokl., 6 (1965), 988–991 | MR

[17] van Montfort K., Visser E., van Draat L. F., “Index tracking by means of optimized sampling”, J. Portfol. Mgmt. 2008., 34:2, 143–151 | DOI | MR

[18] Beasley J. E., Meade N., Chang T.-J., “An evolutionary heuristic for the index tracking problem”, Eur. J. Oper. Res., 148:3 (2003), 621–643 | DOI | MR

[19] Canagkoz N. A., Beasley J. E., “Mixed-integer programming approaches for index tracking and enhanced indexation”, Eur. J. Oper. Res., 196:1 (2008), 384–399 | DOI | MR

[20] Chang T. J., Meade N., Beasley J. E., Sharaiha Y. M., “Heuristics for cardinality constrained portfolio optimisation”, Computers Operations Research, 27:13 (2000), 1271–1302 | DOI

[21] Oriakhi M., Lucas C., Beasley J. E., “Heuristic algorithms for the cardinality constrained efficient frontier”, Eur. J. Oper. Res., 213:13 (2011), 538–550 | DOI | MR

[22] Derigs U., Nickel N.-H., “Meta-heuristic based decision support for portfolio optimization with a case study on tracking error minimization in passive portfolio management”, OR Spectrum, 25:3 (2003), 345–378 | DOI | MR

[23] Maringer D., Oyewumi O., “Index tracking with constrained portfolios”, Intell. Syst. Account., Finance Mgmt., 15:1–2 (2007), 57–71 | DOI

[24] Gilli M., Këllezi E., “The threshold accepting heuristic for index tracking”, Financial Engineering, E-Commerce and Supply Chain, Kluwer, Dordrecht, 2009, 1–18 | DOI

[25] Gilli M., Winker P., “Heuristic optimization methods in econometrics”, Handbook of Computational Econometircs, eds. D. Beasley, E. Kontoghiorghes, John Wiley Sons, Ltd, Chichester, 2009, 81–120 | DOI

[26] Krink T., Mittnik S., Paterlini S., “Differential evolution and combinatorial search for constrained index tracking”, Ann. Oper. Res., 172 (2009), 153, 153–176 | DOI | MR

[27] Coleman T. F., Li Y., Henniger J., “Minimizing tracking error while restricting the number of assets”, J. Risk, 8:4 (2006), 33–56 | DOI

[28] Mehlhorn K., Sanders P., Algorithms and Data Structures, Springer-Verlag, Berlin–Heidelberg, 2008, 300 pp. | DOI | MR

[29] Le T., An H., Mahdi M., “Long-Short Portfolio Optimization Under Cardinality Constraints by Difference of Convex Functions Algorithm”, J. Optim. Theory Appl., 161:1 (2014), 199–224 | DOI | MR

[30] Li Y., Yang X., Zhu S., Li D.-H., “A hybrid approach for index tracking with practical constraints”, J. Ind. Manag. Optim., 10:3 (2014), 905–927 | DOI | MR

[31] Cui T., Cheng S., Bai R., “A combinatorial algorithm for the cardinality constrained portfolio optimization problem”, Proc. of the 2014 IEEE Congress on Evolutionary Computation, CEC 2014, 2014, 491–498 | DOI

[32] Cesarone F., Scozzari A., Tardella F., “A new method for mean-variance portfolio optimization with cardinality constraints”, Ann. Oper. Res., 205:1 (2013), 213–234 | DOI | MR

[33] Gilli M., Schumann E., “Heuristic optimisation in financial modeling”, Ann. Oper. Res., 193:1 (2012), 129–158 | DOI | MR

[34] Das A., Kempe D., “Submodular meets spectral : Greedy algorithms for subset selection,sparse approximation and dictionary selection”, Proc. of the 28th Intern. Conf. on Machine Learning, ICML-11, ACM, N. Y., 2011, 1057–1064

[35] Jeurissen R., A hybrid genetic algorithm to track the dutch AEX-index, Bachelor's thesis, Informatics Economics, Erasmus Univ. Rotterdam, 2005, 36 pp. (Accessed 10.07.2016) https://ru.scribd.com/document/125079765/Jeurissen-Roland-A-Hybrid-Genetic-Algorithm-to-Track-the-Dutch-AEX-Index-2005

[36] Jeurissen R., van den Berg J., “Optimized index tracking using a hybrid genetic algorithm”, Proc. IEEE World Congr. Evolutionary Computation, CEC 2008, 2008, 2327–2334 | DOI

[37] Maringer D., Portfolio Management with Heuristic Optimization, Advances in Comput. Manag. Sci., 8, Springer, Berlin, 2005, 223 pp.

[38] DeMiguel V., Garlappi L., Francisco J., “A Generalized Approach to Portfolio Optimization: Improving Performance by Constraining Portfolio Norms”, Management Science, 55:5 (2009), 798–812 | DOI | MR

[39] Giuzio M., Ferrari D.,Paterlini S., “Sparse and robust normal and $t$-portfolios by penalized $L_q$-likelihood minimization”, EJOR, 250:1 (2016), 251–261 | DOI | MR

[40] Fastrich B., Paterlini S., Winker P., “Cardinality versus $q$-norm constraints for index tracking”, Quantitative Finance, 14:11 (2014), 2019–2032 | DOI | MR

[41] Xu F., Xu Z., Xue H., Sparse index tracking: an $L_{1/2}$ regularization based model and solution, 2012, 19 pp., arXiv: 1506.05867

[42] Ruiz-Torrubiano R., Suárez A., “A memetic algorithm for cardinality-constrained portfolio optimization with transaction costs”, Appl. Soft Comput., 36 (2015), 125–142 | DOI

[43] Xu F., Lu Z., Xu Z., “An efficient optimization approach for a cardinality-constrained index tracking problem”, Optimization Methods and Software, 31:2 (2016), 258–271 | DOI | MR

[44] Yen Y.-M., Yen T.-J., “Solving norm constrained portfolio optimization via coordinate-wise descent algorithms”, Comput. Statist. Data Anal., 76 (2014), 737–759 | DOI | MR

[45] Yen Y.-M., “Sparse Weighted-Norm Minimum Variance Portfolios”, Review of Finance, 20:3 (2015), 1259–1287 | DOI

[46] Xidonas P., Mavrotas G., Psarras J., “Portfolio management within the frame of multiobjective mathematical programming: a categorised bibliographic study”, Intern. J. Oper. Res., 8:1 (2010), 21–41 | DOI | MR

[47] Brito R. P., Vicente L. N., “Efficient cardinality/mean-variance portfolios”, System Modeling and Optimization, IFIP International Federation for Information Processing, 443, Springer, Berlin–Heidelberg, 2014, 52–73 | DOI

[48] Gao J., Li D., “Optimal Cardinality Constrained Portfolio Selection”, Operations Research, 61:3 (2013), 745–761 | DOI | MR

[49] Ye T., Fang S., Deng Z., Jin Q., “Cardinality constrained portfolio selection problem: A completely positive programming approach”, J. Ind. Manag. Optim., 12:3 (2016), 1041–1056 | DOI | MR

[50] Tibshirani R., “Regression Shrinkage and Selection via the Lasso”, J. Royal Statist. Soc. : Ser. B (Statistical Methodology), 58:1 (1996), 267–288 | DOI | MR

[51] Becker S., Candes E. J., Grant M., “Templates for convex cone problems with applications to sparse signal recovery”, Mathematical Programming Computation, 3:3 (2011), 165, 165–218 | DOI | MR

[52] Storn R., Price K., “Differential Evolution — A Simple and Efficient Heuristic for global Optimization over Continuous Spaces”, J. Global Optimization, 11:4 (1997), 341–359 | DOI | MR

[53] Price K., Storn R. M., Lampinen J. A., Differential evolution: a practical approach to global optimization, Springer, Berlin, 2005, 539 pp. | MR

[54] Andriosopoulos K., Doumpos M., Papapostolou N. C., Pouliasis P. K., “Portfolio optimization and index tracking for the shipping stock and freight markets using evolutionary algorithms”, Transportation Research Part E : Logistics and Transportation Review, 52, Spec. iss.: Maritime Financial Management (2013), 16–34 | DOI | MR

[55] Beasley J. E., OR-Library, (Accessed 11.04.2016) http://people.brunel.ac.uk/m̃astjjb/jeb/orlib/indtrackinfo.html