Izvestiya of Saratov University.

Mathematics. Mechanics. Informatics

ISSN 1816-9791 (Print)
ISSN 2541-9005 (Online)

For citation:

Faizliev A. R., Khomchenko A. A., Sidorov S. P. Empirical Analysis of Algorithms for Solving the Index Tracking Problem. Izvestiya of Saratov University. Mathematics. Mechanics. Informatics, 2018, vol. 18, iss. 1, pp. 101-124. DOI: 10.18500/1816-9791-2018-18-1-101-124, EDN: YABQRN

This is an open access article distributed under the terms of Creative Commons Attribution 4.0 International License (CC-BY 4.0).
Published online: 
28.03.2019
Full text:
download
(downloads: 164)
Language: 
Russian
Heading: 
Computer Sciences
Article type: 
Article
UDC: 
519.68
DOI: 
10.18500/1816-9791-2018-18-1-101-124
EDN: 
YABQRN

Empirical Analysis of Algorithms for Solving the Index Tracking Problem

Autors: 
Faizliev Alexey R., Saratov State University
Khomchenko Andrei Anatol'evich, Saratov State University
Sidorov Sergei Petrovich, Saratov State University
Abstract: 

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\&P 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.

Key words: 
index tracking
portfolio optimization
greedy algorithm
LASSO-type regression
differential evolution algorithm
References: 
  1. Markowits H. M. Portfolio Selection // J. Finance. 1952. Vol. 7, № 1. P. 71–91. DOI: https://doi.org/10.1111/j.1540-6261.1952.tb01525.x.
  2. Roll R. A mean/variance analysis of tracking error // J. Portfol. Mgmt. 1992. Vol. 18, № 4. P. 13–22. DOI: https://doi.org/10.3905/jpm.1992.701922.
  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. 2013. Vol. 10, iss 1. P. 21–49. DOI: https://doi.org/10.1007/s10287-012-0158-y.
  4. Brodie J., Daubechiesa I., De Molc C., Giannoned D., Lorisc I. Sparse and stable Markowitz portfolios // PNAS. 2009. Vol. 106, № 30. P. 12267–12272. DOI: https://doi.org/10.1073/pnas.0904287106.
  5. Gilli M., Kellezi E. The threshold accepting heuristic for index tracking // Financial Engineering, E-Commerce and Supply Chain. 2002. P. 1–18. DOI: https://doi.org/10.1007/978-1-4757-5226-7_1.
  6. Prigent J.-L. Portfolio Optimization and Performance Analysis. Boca Raton : Chapman & Hall/CRC, 2007. 456 p.
  7. Rudolf M., Wolter H. J., Zimmermann H. A linear model for tracking error minimization // J. Banking & Finance. 1999. Vol. 23, № 1. P. 85–103. DOI: https://doi.org/10.1016/S03784266(98)00076-4.
  8. DeMiguel V., Garlappi L., Uppal R. Optimal Versus Naive Diversification: How Inefficient is the 1/N Portfolio Strategy? // Rev. Financ. Stud. 2009. Vol. 22, № 5. P. 1915–1953. DOI: https://doi.org/10.1093/rfs/hhm075.
  9. Bertero M., Boccacci P. Introduction to Inverse Problems in Imaging. L. : Institute of Physics Publ., 1998. 352 p. DOI: https://doi.org/10.1887/0750304359.
  10. Chen S. S., Donoho D. L., Saunders M. A. Atomic Decomposition by Basis Pursuit // SIAM Review. 2001. Vol. 43, iss. 1. P. 129–159. DOI: https://doi.org/10.1137/S003614450037906X.
  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. 2004. Vol. 57, iss. 11. P. 1413–1457. DOI: https://doi.org/10.1002/cpa.20042.
  12. Osborne M. R., Presnell B., Turlach B. A. A New Approach to Variable Selection in Least Squares Problems // IMA J. Numer. Anal. 2000. Vol. 20, iss. 3. P. 389–403. DOI: https://doi.org/10.1093/imanum/20.3.389.
  13. Osborne M. R., Presnell B., Turlach B. A. On the LASSO and Its Dual // J. Comput. and Graphical Statistics. 2004. Vol. 9, № 2. P. 319–337. DOI: https://doi.org/10.2307/1390657.
  14. Efron B., Hastie T., Johnstone I., Tibshirani R. Least Angle Regression // Ann. Statist. 2004. Vol. 32, № 2. P. 407–499. DOI: https://doi.org/10.1214/009053604000000067.
  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. P. 1921–1928.
  16.   Tikhonov A. N. Incorrect problems of linear algebra and a stable method for their solution. Sov. Math. Dokl., 1965, vol. 6, pp. 988–991.
  17. van Montfort K., Visser E., van Draat L. F. Index tracking by means of optimized sampling // J. Portfol. Mgmt. 2008. Vol. 34, № 2. p. 143–151. DOI: https://doi.org/10.3905/jpm.2008.701625.
  18. Beasley J. E., Meade N., Chang T.-J. An evolutionary heuristic for the index tracking problem // Eur. J. Oper. Res. 2003. Vol. 148, iss. 3. P. 621–643. DOI: https://doi.org/10.1016/S0377-2217(02)00425-3.
  19. Canagkoz N. A., Beasley J. E. Mixed-integer programming approaches for index trackingand enhanced indexation // Eur. J. Oper. Res. 2008. Vol. 196, iss. 1. P. 384–399. DOI: https://doi.org/10.1016/j.ejor.2008.03.015.
  20. Chang T. J., Meade N., Beasley J. E., Sharaiha Y. M. Heuristics for cardinality constrained portfolio optimisation // Computers & Operations Research. 2000. Vol. 27, iss. 13. P. 1271– 1302. DOI: https://doi.org/10.1016/S0305-0548(99)00074-X.
  21. Oriakhi M., Lucas C., Beasley J. E. Heuristic algorithms for the cardinality constrained efficient frontier // Eur. J. Oper. Res. 2011. Vol. 213, iss. 13. P. 538–550. DOI: https://doi.org/10.1016/j.ejor.2011.03.030.
  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. 2003. Vol. 25, iss. 3. P. 345–378. DOI: https://doi.org/10.1007/s00291-003-0127-5.
  23. Maringer D., Oyewumi O. Index tracking with constrained portfolios // Intell. Syst. Account., Finance Mgmt. 2007. Vol. 15, iss. 1–2. P. 57–71. DOI: https://doi.org/10.1002/isaf.285.
  24. Gilli M., Këllezi E. The threshold accepting heuristic for index tracking // Financial Engineering, E-Commerce and Supply Chain. Dordrecht : Kluwer, 2009. P. 1–18. DOI: https://doi.org/10.1007/978-1-4757-5226-7_1.
  25. Gilli M., Winker P. Heuristic optimization methods in econometrics // Handbook of Computational Econometircs / eds. D. Beasley, E. Kontoghiorghes. Chichester : John Wiley & Sons, Ltd, 2009. P. 81–120. DOI: https://doi.org/10.1002/9780470748916.ch3.
  26. Krink T., Mittnik S., Paterlini S. Differential evolution and combinatorial search for constrained index tracking // Ann. Oper. Res. 2009. Vol. 172. Article 153. P. 153–176. DOI: https://doi.org/10.1007/s10479-009-0552-1.
  27. Coleman T. F., Li Y., Henniger J. Minimizing tracking error while restricting the number of assets // J. Risk. 2006. Vol. 8, № 4. P. 33–56.
  28. Mehlhorn K., Sanders P. Algorithms and Data Structures. Berlin ; Heidelberg : Springer- Verlag, 2008. 300 p. DOI: https://doi.org/10.1007/978-3-540-77978-0.
  29. Le T., An H., Mahdi M. Long-Short Portfolio Optimization Under Cardinality Constraints by Difference of Convex Functions Algorithm // J. Optim. Theory Appl. 2014. Vol. 161,iss. 1. P. 199–224. DOI: https://doi.org/10.1007/s10957-012-0197-0.
  30. Li Y., Yang X., ZHu S.,Li D.-H. A hybrid approach for index tracking with practical constraints // J. Ind. Manag. Optim. 2014. Vol. 10, iss. 3. P. 905–927. DOI: https://doi.org/10.3934/jimo.2014.10.905.
  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. Vol. 18, iss. 1. Article 6900357. P. 491–498.
  32. Cesarone F., Scozzari A., Tardella F. A new method for mean-variance portfolio optimization with cardinality constraints // Ann. Oper. Res. 2013. Vol. 205, iss. 1. P. 213–234. DOI: https://doi.org/10.1007/s10479-012-1165-7.
  33. Gilli M., Schumann E. Heuristic optimisation in financial modeling // Ann. Oper. Res. 2012. Vol. 193, iss. 1. P. 129–158. DOI: https://doi.org/10.1007/s10479-011-0862-y.
  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). N.Y. : ACM, 2011. P. 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 p. Available at: https://ru.scribd.com/document/125079765/Jeurissen-Roland-A-Hybrid-Genet... (Accessed 10 July 2016).
  36. Jeurissen R., van den Berg J. Optimized index tracking using a hybrid genetic algorithm // Proc. IEEE World Congr. Evolutionary Computation (CEC2008). 2008. P. 2327–2334. DOI: https://doi.org/10.1109/CEC.2008.4631108.
  37. Maringer D. Portfolio Management with Heuristic Optimization. Advances in Comput. Manag. Sci. Vol. 8. Berlin : Springer, 2005. 223 p. DOI: https://doi.org/10.1007/b136219.
  38. DeMiguel V., Garlappi L.,Francisco J. A Generalized Approach to Portfolio Optimization: Improving Performance by Constraining Portfolio Norms // Management Science. 2009. Vol. 55, iss. 5. P. 798–812.
  39. Giuzio M., Ferrari D.,Paterlini S. Sparse and robust normal and t-portfolios by penalized L q -likelihood minimization // EJOR. 2016. Vol. 250, iss. 1. P. 251–261. DOI: https://doi.org/10.1016/j.ejor.2015.08.056.
  40. Fastrich B., Paterlini S., Winker P. Cardinality versus q-norm constraints for index tracking // Quantitative Finance. 2014. Vol. 14, iss. 11. P. 2019–2032. DOI: https://doi.org/10.1080/14697688.2012.691986.
  41. Xu F., Xu Z., Xue H. Sparse index tracking: an L 1/2 regularization based model and solution // Working Paper. arXiv:1506.05867. 2012. P. 1–19.
  42. Ruiz-Torrubiano R., Su árez A. A memetic algorithm for cardinality-constrained portfolio optimization with transaction costs // Appl. Soft Comput. 2015. Vol. 36. P. 125–142. DOI: https://doi.org/10.1016/j.asoc.2015.06.053.
  43. Xu F., Lu Z., Xu Z. An efficient optimization approach for a cardinality-constrained index tracking problem // Optimization Methods and Software. 2016. Vol. 31, iss. 2. P. 258–271. DOI: https://doi.org/10.1080/10556788.2015.1062891.
  44. Yen Y.-M., Yen T.-J. Solving norm constrained portfolio optimization via coordinate-wise descent algorithms // Comput. Statist. & Data Anal. 2014. Vol. 76. P. 737–759. DOI: https://doi.org/10.1016/j.csda.2013.07.010.
  45. Yen Y.-M. Sparse Weighted-Norm Minimum Variance Portfolios // Review of Finance. 2015. Vol. 20, iss. 3. P. 1259–1287. DOI: https://doi.org/10.1093/rof/rfv024.
  46. Xidonas P., Mavrotas G., Psarras J. Portfolio management within the frame of multiobjective mathematical programming: a categorised bibliographic study // Intern. J. Oper. Res. 2010. Vol. 8, iss. 1. P. 21–41. DOI: https://doi.org/10.1504/IJOR.2010.033102.
  47. Brito R. P., Vicente L. N Efficient cardinality/mean-variance portfolios // System Modeling and Optimization. IFIP International Federation for Information Processing. Vol. 443. Berlin, Heidelberg : Springer, 2014. P. 52–73. DOI: https://doi.org/10.1007/978-3-662-45504-3_6.
  48. Gao J., Li D. Optimal Cardinality Constrained Portfolio Selection // Operations Research. Vol. 61, iss. 3. P. 745–761. DOI: https://doi.org/10.1287/opre.2013.1170.
  49. Ye T., Fang S, Deng Z., Jin Q. Cardinality constrained portfolio selection problem: A completely positive programming approach // J. Ind. Manag. Optim. 2016. Vol. 12, iss. 3. P. 1041–1056. DOI: https://doi.org/10.3934/jimo.2016.12.1041.
  50. Tibshirani R. Regression Shrinkage and Selection via the Lasso // J. Royal Statist. Soc. : Ser. B (Statistical Methodology). 1996. Vol. 58, № 1. P. 267–288. DOI: https://doi.org/10.1111/j.1467-9868.2011.00771.x.
  51. Becker S., Candes E. J., Grant M. Templates for convex cone problems with applications to sparse signal recovery // Mathematical Programming Computation. 2011. Vol. 3, iss. 3. Article 165. P. 165–218. DOI: https://doi.org/10.1007/s12532-011-0029-5.
  52. Storn R., Price K. Differential Evolution — A Simple and Efficient Heuristic for global Optimization over Continuous Spaces // J. Global Optimization. 1997. Vol. 11, iss. 4. P. 341–359. DOI: https://doi.org/10.1023/A:1008202821328.
  53. Price K., Storn R. M., Lampinen J. A. Differential evolution: a practical approach to global optimization. Berlin : Springer, 2005. 539 p.
  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. 2013. Vol. 52. Spec. iss. : Maritime Financial Management. P. 16–34. DOI: https://doi.org/10.1016/j.tre.2012.11.006.
  55. Beasley J. E. OR-Library. URL: http://people.brunel.ac.uk/mastjjb/jeb/orlib/indtrackinfo.html (Accessed 11 April 2016).
Received: 
18.10.2017
Accepted: 
11.02.2018
Published: 
28.03.2018
Short text (in English):
download
(downloads: 97)
  • 1311 reads