Известия Саратовского университета. Новая серия.

Серия Математика. Механика. Информатика

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

Для цитирования:

Файзлиев А. Р., Хомченко А. А., Сидоров С. П. Эмпирический анализ работы алгоритмов решения задачи репликации индекса // Известия Саратовского университета. Новая серия. Серия: Математика. Механика. Информатика. 2018. Т. 18, вып. 1. С. 101-124. DOI: 10.18500/1816-9791-2018-18-1-101-124, EDN: YABQRN

Статья опубликована на условиях лицензии Creative Commons Attribution 4.0 International (CC-BY 4.0).
Опубликована онлайн: 
28.03.2019
Полный текст:
скачать
(downloads: 225)
Язык публикации: 
русский
Рубрика: 
Информатика
Тип статьи: 
Научная статья
УДК: 
519.68
DOI: 
10.18500/1816-9791-2018-18-1-101-124
EDN: 
YABQRN

Эмпирический анализ работы алгоритмов решения задачи репликации индекса

Авторы: 
Файзлиев Алексей Раисович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Хомченко Андрей Анатольевич, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Сидоров Сергей Петрович, Саратовский национальный исследовательский государственный университет имени Н. Г. Чернышевского
Аннотация: 

Стратегия слежения за индексом (репликация индекса) - это пассивная финансовая стратегия, которая состоит в имитации (репликации) доходности заданного индекса или портфеля. Цель инвестора - найти веса активов в своем портфеле, чтобы получившийся портфель имел минимальную ошибку слежения, в качестве которой обычно используют дисперсию разности между доходностью индекса и доходностью портфеля. В данной работе решение проблемы слежения за индексом рассматривается с ограничением на кардинальность, т. е. с ограничением на максимальное количество активов, удерживаемых в портфеле. Задача слежения за индексом с ограничением на кардинальность является задачей неполиномиальной сложности и, как правило, требует разработки эвристических алгоритмов. В статье рассматриваются различные алгоритмы решения данной задачи в норме l_2, в частности, жадный алгоритм, алгоритм дифференциальной эволюции и алгоритм типа LASSO. Для проведения эмпирического анализа были использованы открытые данные, относящиеся к трем основным рыночным индексам - Hang Seng (Гонконг), S&P 100 (США) и Nikkei 225 (Япония). Для сравнительного анализа жадного алгоритма с алгоритмом типа LASSO и с алгоритмом дифференциальной эволюции была использована процедура скользящего временного окна. При этом сравнение подходов происходило как по внутривыборочным, так и по вневыборочным данным.

Ключевые слова: 
слежение за индексом
оптимизация портфеля
жадные алгоритмы
регрессии типа LASSO
алгоритм дифференциальной эволюции
Список источников: 
  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. Тихонов А. Н. О некорректных задачах линейной алгебры и устойчивом методе их решения // Докл. АН СССР. 1965. Т. 163, № 3. С. 591–594.
  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. URL: https://ru.scribd.com/document/125079765/Jeurissen-Roland-A-Hybrid-Genet... (дата обращения: 10.07.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 (дата обращения: 11.04.2016).
Поступила в редакцию: 
18.10.2017
Принята к публикации: 
11.02.2018
Опубликована: 
28.03.2018
Краткое содержание:
скачать
(downloads: 144)
  • 1590 просмотров