×

Optimal online algorithms for the portfolio selection problem, bi-directional trading and -search with interrelated prices. (English) Zbl 1430.91090

The authors describe three types of the portfolio selection problems. Namely, the problem P1 consists in allocating wealth to a set of stocks in a capital market; for this allocation to be optimal, knowledge about the performance of the assets in the next trading period is needed. The problem P2 is a bi-directional trading problem. Here one trades (or converts) back and forth between two assets and aims at maximizing the amount of units of one asset. Another version of P2 is the so called bi-directional search problem P3 that is a special instance of P2; here an investor is allowed to trade back and forth between two assets; however, the trade is “all or nothing”. In the paper, the authors develop a competitive portfolio selection algorithm called optimal portfolio for interrelated prices (OPIP) with the offline benchmark. OPIP solves P1 optimally when maximal upward and downward relative price changes of each asset are known. In order to derive OPIP, the authors first apply the concept of competitive analysis to P1. OPIP is competitive and optimal. Based on the ideas of OPIP, they derive the new online algorithm optimal conversion for interrelated prices (OCIP) which solves P2 optimally online when an investor is allowed to be arbitrarily invested in two assets; note that OCIP can also be applied, when the interrelated price bounds are unknown. Based on OCIP, they derive the bi-directional and optimal online search for unknown relative price bounds algorithm for P3. Finally, they carry out a numerical testing to evaluate the performance of these algorithms.

MSC:

91G10 Portfolio theory
68W27 Online algorithms; streaming algorithms

Software:

PAMR
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] A. Agarwal, E. Hazan, S. Kale and R.E. Schapire, Algorithms for portfolio management based on the newton method. In: Proceedings of the 23rd International Conference on Machine Learning. ACM (2006) 9-16.
[2] N. Boria and V.T. Paschos, A survey on combinatorial optimization in dynamic environment. RAIRO: OR 45 (2011) 241-294. · Zbl 1254.90186 · doi:10.1051/ro/2011114
[3] A. Borodin, R. El-Yaniv and V. Gogan, On the competitive theory and practice of portfolio selection (Extended Abstract). In: Proceedings of the 4th Latin American Symposium on Theoretical Informatics (2000) 173-196. · Zbl 0966.91039
[4] A. Borodin, R. El-Yaniv and V. Gogan, Can we learn to beat the best stock. J. Artif. Intell. Res. AI Access Found. 21 (2004) 579-594. · Zbl 1076.91015
[5] G.-H. Chen, M.-Y. Kao, Y.-D. Lyuu and H.-K. Wong, Optimal buy-and-hold strategies for financial markets with bounded daily returns. SIAM J. Comput. 31 (2001) 447-459. · Zbl 1160.91349 · doi:10.1137/S0097539799358847
[6] T. Cover, Universal portfolios. Math. Finance 1 (1991) 1-29. · Zbl 0900.90052 · doi:10.1111/j.1467-9965.1991.tb00002.x
[7] R. Dochow, Online Algorithms for the Portfolio Selection Problem. Springer, Berlin (2016). · Zbl 1358.91001
[8] C. Gangolf, R. Dochow, G. Schmidt and T. Tamisier, Automated credit rating prediction in a competitive framework. RAIRO: OR 50 (2016) 749-765. · Zbl 1358.91106 · doi:10.1051/ro/2016030
[9] D. Helmbold, R. Schapire, Y. Singer and M. Warmuth, On-line portfolio selection using multiplicative updates. Math. Finance 8 (1998) 325-347. · Zbl 1021.91032 · doi:10.1111/1467-9965.00058
[10] D. Huang, J. Zhou, B. Li, S.C. Hoi and S. Zhou, Robust median reversion strategy for on-line portfolio selection. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence (2013) 2006-2012.
[11] A. Kalai and S. Vempala, Efficient algorithms for universal portfolios. J. Mach. Learn. Res. 3 (2002) 423-440. · Zbl 1104.91035
[12] B. Li, P. Zhao, S. Hoi and V. Gopalkrishnan, PAMR: passive aggressive mean reversion strategy for portfolio selection. Mach. Learn. 87 (2012) 221-258. · Zbl 1238.91128
[13] G. Schmidt, Competitive analysis of bi-directional non-preemptive conversion. J. Comb. Optim. 34 (2017) 1096-1113. · Zbl 1374.68727
[14] P. Schroeder, R. Dochow and G. Schmidt, Conversion algorithms with a reward function and interrelated conversion rates. In: Proceedings of the 45th International Conference on Computers and Industrial Engineering. France (2015) 536-543.
[15] P. Schroeder and I. Kacem, Optimal cash management with uncertain and interrelated demands. In: Proceedings of the 47th International Conference on Computers and Industrial Engineering. Portugal (2017) 502-508.
[16] P. Schroeder, R. Dochow and G. Schmidt, Optimal solutions for the online time series search and one-way trading problem with interrelated prices and a profit function. Comput. Ind. Eng. 119 (2018) 465-471.
[17] D.D. Sleator and R.E. Tarjan, Amortized efficiency of list update and paging rules. Commun. ACM 28 (1985) 202-208.
[18] R. El-Yaniv, A. Fiat, R. Karp and G. Turpin, competitive analysis of financial games. In: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (1992) 327-333. · Zbl 0977.68504
[19] W. Zhang, Y. Xu, F. Zheng and Y. Dong, Optimal algorithms for online time series search and one-way trading with interrelated prices. J. Comb. Optim. 23 (2012) 159-166. · Zbl 1247.90225
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.