Performance guaranteeing algorithms for solving online decision problems in financial systems
Algorithmes à performance garantie pour des problèmes de décision financière en ligne
Résumé
This thesis contains several online financial decision problems and their solutions. The problems are formulated as online problems (OP) and online algorithms (OA) are created to solve them. Due to the fact that there can be various OA for the same OP, there must be some criteria with which one can make statements about the quality of an OA. In this thesis these criteria are the competitive ratio (c), the competitive difference (cd) and the numerical performance. An OA with a lower c is preferable to another one with a higher value. An OA that has the lowest c is called optimal. We consider the following OPS. The online conversion problem (OCP), the online portfolio selection problem (PSP) and the cash management problem (CMP). After the introductory chapter, the OPs, the notation and the state of the art in the field of OPs is presented. In the third chapter, three variants of the OCP with interrelated prices are solved. In the fourth chapter the time series search with interrelated prices is revisited and new algorithms are created. At the end of the chapter, the optimal OA k-DIV for the general k-max search with interrelated prices is developed. In Chapter 5 the PSP with interrelated prices is solved. The created OA OPIP is optimal. Using the idea of OPIP, an optimal OA for the two-way trading is created (OCIP). Having OCIP, an optimal OA for the bi-directional search knowing the values of θ_1 and θ_2 is created (BUND). For unknown θ_1 and θ_2, the optimal OA RUNis created. The chapter ends with an empirical (for OPIP) and experimental (for OCIP, BUND and RUN) testing. Chapters 6 and 7 deal with the CMP. In both of them, a numerical testing is done in order to compare the numerical performance of the new OAs to the one of the already established ones. In Chapter 6 an optimal OA is constructed; in Chapter 7, OAs are designed which minimize cd. The OA BCSID solves the CMP with interrelated demands to optimality. The OA aBBCSID solves the CMP when the values of de θ_1, θ_2,m and M are known; however, this OA is not optimal. In Chapter 7 the CMP is solved, knowing m and M and minimizing cd (OA MRBD). For the interrelated demands, a heuristic OA (HMRID) and a cd-minimizing OA (MRID) is presented. HMRID is good compromise between the numerical performance and the minimization of cd. The thesis concludes with a short discussion about shortcomings of the considered OPs and the created OAs. Then some remarks about future research possibilities in this field are given.
Cette thèse contient quelques problèmes de décision financière en ligne et des solutions. Les problèmes sont formulés comme des problèmes en ligne (OP) et des algorithmes en ligne (OA) sont créés pour résoudre. Comme il peut y avoir plusieurs OAs pour le même OP, il doit y avoir un critère afin de pouvoir faire des indications au sujet de la qualité d’un OA. Dans cette thèse ces critères sont le ratio compétitif (c), la différence compétitive (cd) et la performance numérique. Un OA qui a un c ou cd plus bas qu’un autre est à préférer. Un OA qui possède le c le plus petit est appelé optimal. Nous considérons les OPs suivants. Le problème de conversion en ligne (OCP), le problème de sélection de portefeuille en ligne (PSP) et le problème de gestion de trésorerie en ligne (CMP). Après le premier chapitre d’introduction, les OPs, la notation et l’état des arts dans le champ des OPs sont présentés. Dans le troisième chapitre on résoudre trois variantes des OCP avec des prix interconnectés. En Chapitre 4 on travaille encore sur le problème de recherche de série chronologie avec des prix interconnectés et on construit des nouveaux OAs. À la fin de ce chapitre l’OA k-DIV est créé pour le problème de recherche générale des k maximums. k-DIV est aussi optimal. En Chapitre 5 on résout le PSP avec des prix interconnectés. L’OA créé s’appelle OPIP et est optimal. En utilisant les idées de OPIP, on construit un OA pour le problème d’échange bidirectionnel qui s’appelle OCIP et qui est optimal. Avec OPIP, on construit un OA optimal pour le problème de recherche bidirectionnel (OA BUND) sachant les valeurs de θ_1 et θ_2. Pour des valeurs inconnues, on construit l’OA RUN qui est aussi optimal. Les chapitres 6 et 7 traitent sur le CMP. Dans les deux chapitres il y a des tests numériques afin de pouvoir comparer la performance des OAs nouveaux avec celle des OAs déjà établies. En Chapitre 6 on construit des OAs optimaux ; en chapitre 7 on construit des OA qui minimisent cd. L’OA BCSID résoudre le CMP avec des demandes interconnectées ; LOA aBBCSID résoudre le problème lorsqu’ on connaît les valeurs de θ_1,θ_2,m et M. L’OA n’est pas optimal. En Chapitre 7 on résout le CMP par rapport à m et M en minimisant cd (OA MRBD). Ensuite on construit l’OA HMRID et l’OA MRID pour des demandes interconnectées. MRID minimise cd et HMRID est un bon compromis entre la performance numérique et la minimisation de cd.