Optimal online algorithms for the portfolio selection problem, bi-directional trading and -search with interrelated prices
RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 2, pp. 559-576.

In this work we investigate the portfolio selection problem (P1) and bi-directional trading (P2) when prices are interrelated. Zhang et al. (J. Comb. Optim. 23 (2012) 159–166) provided the algorithm UND which solves one variant of P2. We are interested in solutions which are optimal from a worst-case perspective. For P1, we prove the worst-case input sequence and derive the algorithm optimal portfolio for interrelated prices (OPIP). We then prove the competitive ratio and optimality. We use the idea of OPIP to solve P2 and derive the algorithm called optimal conversion for interrelated prices (OCIP). Using OCIP, we also design optimal online algorithms for bi-directional search (P3) called bi-directional UND (BUND) and optimal online search for unknown relative price bounds (RUN). We run numerical experiments and conclude that OPIP and OCIP perform well compared to other algorithms even if prices do not behave adverse.

Reçu le :
Accepté le :
DOI : 10.1051/ro/2018064
Classification : 90C27
Mots-clés : Competitive analysis, portfolio selection, two-way trading, online algorithms, bi-directional search
Schroeder, Pascal 1 ; Kacem, Imed 1 ; Schmidt, Günter 1

1 
@article{RO_2019__53_2_559_0,
     author = {Schroeder, Pascal and Kacem, Imed and Schmidt, G\"unter},
     title = {Optimal online algorithms for the portfolio selection problem, bi-directional trading and -search with interrelated prices},
     journal = {RAIRO - Operations Research - Recherche Op\'erationnelle},
     pages = {559--576},
     publisher = {EDP-Sciences},
     volume = {53},
     number = {2},
     year = {2019},
     doi = {10.1051/ro/2018064},
     zbl = {1430.91090},
     language = {en},
     url = {http://archive.numdam.org/articles/10.1051/ro/2018064/}
}
TY  - JOUR
AU  - Schroeder, Pascal
AU  - Kacem, Imed
AU  - Schmidt, Günter
TI  - Optimal online algorithms for the portfolio selection problem, bi-directional trading and -search with interrelated prices
JO  - RAIRO - Operations Research - Recherche Opérationnelle
PY  - 2019
SP  - 559
EP  - 576
VL  - 53
IS  - 2
PB  - EDP-Sciences
UR  - http://archive.numdam.org/articles/10.1051/ro/2018064/
DO  - 10.1051/ro/2018064
LA  - en
ID  - RO_2019__53_2_559_0
ER  - 
%0 Journal Article
%A Schroeder, Pascal
%A Kacem, Imed
%A Schmidt, Günter
%T Optimal online algorithms for the portfolio selection problem, bi-directional trading and -search with interrelated prices
%J RAIRO - Operations Research - Recherche Opérationnelle
%D 2019
%P 559-576
%V 53
%N 2
%I EDP-Sciences
%U http://archive.numdam.org/articles/10.1051/ro/2018064/
%R 10.1051/ro/2018064
%G en
%F RO_2019__53_2_559_0
Schroeder, Pascal; Kacem, Imed; Schmidt, Günter. Optimal online algorithms for the portfolio selection problem, bi-directional trading and -search with interrelated prices. RAIRO - Operations Research - Recherche Opérationnelle, Tome 53 (2019) no. 2, pp. 559-576. doi : 10.1051/ro/2018064. http://archive.numdam.org/articles/10.1051/ro/2018064/

[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

[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

[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

[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

[6] T. Cover , Universal portfolios. Math. Finance 1 (1991) 1–29. | Zbl

[7] R. Dochow , Online Algorithms for the Portfolio Selection Problem. Springer, Berlin (2016).

[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

[9] D. Helmbold , R. Schapire , Y. Singer and M. Warmuth , On-line portfolio selection using multiplicative updates. Math. Finance 8 (1998) 325–347. | Zbl

[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

[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

[13] G. Schmidt , Competitive analysis of bi-directional non-preemptive conversion. J. Comb. Optim. 34 (2017) 1096–1113. | Zbl

[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

[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

Cité par Sources :