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.
Accepté le :
DOI : 10.1051/ro/2018064
Mots-clés : Competitive analysis, portfolio selection, two-way trading, online algorithms, bi-directional search
@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://www.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://www.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://www.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://www.numdam.org/articles/10.1051/ro/2018064/
[1] Algorithms for portfolio management based on the newton method. In: Proceedings of the 23rd International Conference on Machine Learning. ACM (2006) 9–16.
, , and ,[2] A survey on combinatorial optimization in dynamic environment. RAIRO: OR 45 (2011) 241–294. | Zbl
and ,[3] 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
, and ,[4] Can we learn to beat the best stock. J. Artif. Intell. Res. AI Access Found. 21 (2004) 579–594. | Zbl
, and ,[5] Optimal buy-and-hold strategies for financial markets with bounded daily returns. SIAM J. Comput. 31 (2001) 447–459. | Zbl
, , and ,[6] Universal portfolios. Math. Finance 1 (1991) 1–29. | Zbl
,[7] Online Algorithms for the Portfolio Selection Problem. Springer, Berlin (2016).
,[8] Automated credit rating prediction in a competitive framework. RAIRO: OR 50 (2016) 749–765. | Zbl
, , and ,[9] On-line portfolio selection using multiplicative updates. Math. Finance 8 (1998) 325–347. | Zbl
, , and ,[10] Robust median reversion strategy for on-line portfolio selection. In: Proceedings of the 23rd International Joint Conference on Artificial Intelligence (2013) 2006–2012.
, , , and ,[11] Efficient algorithms for universal portfolios. J. Mach. Learn. Res. 3 (2002) 423–440. | Zbl
and ,[12] PAMR: passive aggressive mean reversion strategy for portfolio selection. Mach. Learn. 87 (2012) 221–258. | Zbl
, , and ,[13] Competitive analysis of bi-directional non-preemptive conversion. J. Comb. Optim. 34 (2017) 1096–1113. | Zbl
,[14] 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.
, and ,[15] Optimal cash management with uncertain and interrelated demands. In: Proceedings of the 47th International Conference on Computers and Industrial Engineering. Portugal (2017) 502–508.
and ,[16] 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.
, and ,[17] Amortized efficiency of list update and paging rules. Commun. ACM 28 (1985) 202–208.
and ,[18] competitive analysis of financial games. In: Proceedings of the 33rd Annual Symposium on Foundations of Computer Science (1992) 327–333. | Zbl
, , and ,[19] Optimal algorithms for online time series search and one-way trading with interrelated prices. J. Comb. Optim. 23 (2012) 159–166. | Zbl
, , and ,Cité par Sources :