Для цитирования:
Файзлиев А. Р., Хомченко А. А., Сидоров С. П. Эмпирический анализ работы алгоритмов решения задачи репликации индекса // Известия Саратовского университета. Новая серия. Серия : Математика. Механика. Информатика. 2018. Т. 18, вып. 1. С. 101-124. DOI: 10.18500/1816-9791-2018-18-1-101-124, EDN: YABQRN
Эмпирический анализ работы алгоритмов решения задачи репликации индекса
Стратегия слежения за индексом (репликация индекса) - это пассивная финансовая стратегия, которая состоит в имитации (репликации) доходности заданного индекса или портфеля. Цель инвестора - найти веса активов в своем портфеле, чтобы получившийся портфель имел минимальную ошибку слежения, в качестве которой обычно используют дисперсию разности между доходностью индекса и доходностью портфеля. В данной работе решение проблемы слежения за индексом рассматривается с ограничением на кардинальность, т. е. с ограничением на максимальное количество активов, удерживаемых в портфеле. Задача слежения за индексом с ограничением на кардинальность является задачей неполиномиальной сложности и, как правило, требует разработки эвристических алгоритмов. В статье рассматриваются различные алгоритмы решения данной задачи в норме l_2, в частности, жадный алгоритм, алгоритм дифференциальной эволюции и алгоритм типа LASSO. Для проведения эмпирического анализа были использованы открытые данные, относящиеся к трем основным рыночным индексам - Hang Seng (Гонконг), S&P 100 (США) и Nikkei 225 (Япония). Для сравнительного анализа жадного алгоритма с алгоритмом типа LASSO и с алгоритмом дифференциальной эволюции была использована процедура скользящего временного окна. При этом сравнение подходов происходило как по внутривыборочным, так и по вневыборочным данным.
- 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.
- 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.
- 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.
- 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.
- 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.
- Prigent J.-L. Portfolio Optimization and Performance Analysis. Boca Raton : Chapman & Hall/CRC, 2007. 456 p.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Тихонов А. Н. О некорректных задачах линейной алгебры и устойчивом методе их решения // Докл. АН СССР. 1965. Т. 163, № 3. С. 591–594.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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).
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- Price K., Storn R. M., Lampinen J. A. Differential evolution: a practical approach to global optimization. Berlin : Springer, 2005. 539 p.
- 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.
- Beasley J. E. OR-Library. URL: http://people.brunel.ac.uk/mastjjb/jeb/orlib/indtrackinfo.html (дата обращения: 11.04.2016).
- 1467 просмотров