Submitted by Geandra Rodrigues (geandrar@gmail.com) on 2018-05-23T12:11:21Z No. of bitstreams: 1 joaodanielmadureirayamim.pdf: 873324 bytes, checksum: 5025e3943c3bb2f1e1f19c55767c683e (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-05-24T17:47:46Z (GMT) No. of bitstreams: 1 joaodanielmadureirayamim.pdf: 873324 bytes, checksum: 5025e3943c3bb2f1e1f19c55767c683e (MD5) / Made available in DSpace on 2018-05-24T17:47:46Z (GMT). No. of bitstreams: 1 joaodanielmadureirayamim.pdf: 873324 bytes, checksum: 5025e3943c3bb2f1e1f19c55767c683e (MD5) Previous issue date: 2018-02-23 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Desde o trabalho seminal de Harry Markowitz, em 1952, que iniciou a moderna te-oria de carteiras, as estratégias de alocação de portfólio foram intensamente discutidas na literatura. Com o desenvolvimento de técnicas de otimização online, os algoritmos de aprendizado dinâmico se mostraram uma abordagem efetiva para construir portfólios (COVER, 1991; ARGAWAL et al., 2006). No entanto, poucos trabalhos conectam a lite-ratura tradicional, evoluída a partir do trabalho de Markowitz (1952) com a literatura de otimização online, que evoluiu a partir do trabalho de Cover (1991). O principal objetivo deste trabalho é implementar técnicas de otimização convexa online para: (i) executar estratégias de alocação de portfólio; (ii) conectar esses algoritmos com fatores risco usados em metodologias tradicionais. Dois métodos de algoritmos online foram implementados e adaptados, o Online Gradient Descendent (OGD) e o Online Newton Step (ONS). Além disso, duas novas versões para o algoritmo OGD são propostas para controlar o risco em carteiras. O primeiro, busca limitar o investimento máximo para ações e, o segundo, visa controlar o /3 das carteiras. Ambas as estratégias foram comparadas com o Uniform Constant Rebalanced Portfolio (UCRP) e o Dow Jones Industrial Index (DJIA). Foram utilizados dados do DJIA de março de 1987 até fevereiro de 2009 com observações se-manais. O algoritmo OGD apresentou o maior retorno acumulado entre as estratégias testadas. Ambos os algoritmos (OGD e ONS) apresentaram melhor desempenho do que o UCRP e DJIA ao longo do período. Além disso, o mecanismo de controle de risco pro-posto provou ser uma ferramenta útil para melhorar os resultados relacionados ao valor em risco (VaR) e ao valor condicional em risco (CVaR) das carteiras. / Since the seminal work of Harry Markowitz (1952), which initiated the modern theory of portfolios, the strategies of portfolio allocation were extensively discussed in economic literature. With the development of online optimization techniques, dynamic learning algorithms emerged as an effective approach to develop investment portfolios (COVER, 1991; ARGAWAL et al., 2006). However, there are few attempts aiming to connect the traditional literature of portfolio investment, which evolved based on Markowitz (1952) work, with the recent online methods, developed from Cover (1991). The main objec-tive of this work is to implement online convex optimization techniques to: (i) perform strategies of portfolio allocation; (ii) couple these algorithms with risk factors used in traditional models. Two methods of online algorithms were implemented and adapted, the Online Gradient Descendent (OGD) and the Online Newton Step (ONS). Besides, two new versions for the OGD algorithm are proposed in order to control risk in portfolios. The first one, seeks to limit maximum investment for stocks and, the second, aims to keep control of the /3 of portfolios. Both strategies were compared with the Uniform Constant Re-Balanced Portfolio (UCRP) and the Dow Jones Industrial Index (DJIA). Data from weekly observations of DJIA from March 1987 until February 2009 are used. The OGD algorithm presented the best accumulated return among all strategies. Both algorithms (OGD and ONS) performed better than the UCRP and DJIA index. Furthermore, the risk control mechanism proposed proved to be an useful tool in order to improve results related to the Value at Risk (VaR) and Conditional Value at Risk (CVaR) of the portfolios.

Extremsökande reglering (ESC) är en modellfri adaptiv reglermetod som kan användas för att lokalisera den optimala arbetspunkten i olinjära processer. Det har nyligen visats att det finns problem med traditionell ESC om det reglerade systemet är dynamiskt. I den här avhandlingen behandlar vi en ny metod för extremsökande reglering som är applicerbar för både statiska och dynamiska system. Metoden är baserad på att reglera processens arbetspunkt tills det lokala fasskiftet hos processen når ⇡/2. Resultatet är baserat på det faktum att fasskiftet hos processer generellt förändras kraftigt kring optimum, och för låga frekvenser motsvarar optimum ett fasskift på ⇡/2radianer. Regulatorstrukturen som används liknar en faslåst slinga (PLL). Ett olinjärt Kalmanfilter används för att estimera fasen och en integrerande regulator används för att justera arbetspunkten tills fasen når det önskade fasskiftet. Resultaten är illustrerade i ett exempel där den nya regulatorstrukturen används för att optimera produktionen i en kemisk reaktor. / Extremum Seeking Control (ESC) is a model-free adaptive control method to locate and track the optimal working point for nonlinear plants. However, as shown recently, traditional ESC methods may not work well for dynamic systems. In this thesis, we consider a novel ESC loop to locate the optimal operating point for both static and dynamic systems. Considering that the phase-lag of the system undergoes a large shift near a steady-state optimum and reaches the value of ⇡/2attheoptimaloperatingpoint, thenovelESC applies the phase-lag of the target system to track the optimum. An ex-tended Kalman filter is used to ensure the accuracy of the phase estimation. The structure of a phase locked loop (PLL) is employed in combination with an integral controller to lock the phase near ⇡/2, such that the target system will operate near the optimal working point. The controller is demonstrated by application to optimization of the substrate conversion in a chemical re-actor.

L’autopartage est une manière moderne de louer une voiture. C'est un système attractif pour les clients qui utilisent une voiture occasionnellement. Dans un système d’autopartage, une flotte de véhicules est répartie sur une aire urbaine. Les client peuvent prendre ou rendre une voiture à n'importe quel moment et à n'importe quelle station, à condition qu’il y ait une voiture de libre à la station de départ et qu’il y a une place de parking libre à la station de destination. Pour s'en assurer, les clients peuvent réserver une voiture en avance. Pour qu’un tel système fonctionne de manière satisfaisante, il faut que le nombre de véhicules et le nombre de places libres dans les stations s'équilibrent. Cela conduit à un problème d'équilibre d'occupation des stations, appelé problème de relocalisation : un opérateur doit surveiller l'occupation des stations et décider quand et de quelle manière les voiture doivent être deplacées d’une station « trop pleine » à une station « insuffisamment pleine ». Nous considérons un système d’autopartage innovant, où les voitures sont partiellement autonomes. Cela permet de constituer des convois de véhicules que dirige un véhicule spécial, de sorte qu'un convoi est mis en mouvement par un seul conducteur. Cette configuration est similaire au système mis en place pour les vélos en libre-service, où un camion peut déplacer plusieurs vélos simultanément pendant le processus de la relocalisation. Dans le cadre de cette thèse, nous développons les aspects dynamiques et statiques du problème de relocalisation. Le « problème de relocalisation dynamique » décrit la situation où les voitures sont déplacées pendant les heures de travail afin de satisfaire les besoins des clients. L’opérateur doit prendre des décisions « dynamiques », en fonction de la situation. Dans le cadre du « problème de relocalisation statique », nous supposons qu’il n'y a aucune interaction (ou très peu) entre les clients et le système. Cette situation se produit lorsque le système est préparé pour le lendemain (ex : processus de la relocalisation effectué pendant la nuit). Nous modélisons le problème de relocalisation dans le cadre d’un système de tâches métriques. Ensuite, nous analysons les deux problèmes et nous donnons des stratégies pour les résoudre. Enfin, nous effectuons quelques expériences de calcul pour examiner l’applicabilité des algorithmes présentés en pratique. / Carsharing is a modern way of car rental, attractive to customers who make only occasional use of a car on demand. In a carsharing system, a fleet of cars is distributed at specified stations in an urban area, customers can take a car at any time and station and return it at any time and station, provided that there is a car available at the start station and a free place at the destination station. To ensure the latter, customers have to book their demands in advance. For operating such a system in a satisfactory way, the stations have to keep a good ratio between the total number of places and the number of cars in each station, in order to serve as many requests as possible. This leads to the problem of balancing the load of the stations, called Relocation Problem: an operator has to monitor the load and to decide when and how to move cars from “overfull” stations to “underfull” ones. We consider an innovative carsharing system, where the cars are partly autonomous, which allows to build wireless convoys of cars leaded by a special vehicle, such that the whole convoy is moved by only one driver. This setting is similar to bikesharing, where trucks can simultaneously move several bikes during the relocation process. In this thesis, we address the dynamic and static aspects of the Relocation Problem. The “Dynamic Relocation Problem” describes the situation when cars can be moved between stations during the working hours in order to satisfy the needs of the customers. Hereby, the operator has to make decisions dynamically according to the current situation. In the “Static Relocation Problem” we assume that there is no (or only little) interaction by customers with the system. This situation occurs when the carsharing system is prepared for the next day, i.e., the relocation process is performed during the night. We model the Relocation Problem in the framework of a metric task system. Afterwards, we theoretically analyze both problems and give strategies to solve them. Finally, we perform some computational experiments to examine the applicability of the presented algorithms in practice.

No description available.

La forte variabilité des trafics est devenue l'un des problèmes majeurs auxquels doivent faire face les gestionnaires d'infrastructures réseau. Dans ces conditions, l'optimisation du routage des flux en se basant uniquement sur une matrice de trafic moyenne estimée en heure de pointe n'est plus pertinente. Les travaux conduits dans cette thèse visent la conception de méthodes d'optimisation dynamiques du routage, adaptant en temps réel les routes utilisées par les flux aux conditions de trafic dans le réseau.Nous étudions tout d'abord le problème d'optimisation des poids OSPF pour le routage intra-domaine dans les réseaux IP, où le trafic est routé le long de plus courts chemins, en fonction des poids des liens. Nous proposons une approche en ligne permettant de reconfigurer dynamiquement les poids OSPF, et donc les routes utilisées, pour répondre aux variations observées du trafic et réduire ainsi le taux de congestion du réseau. L'approche proposée repose sur l'estimation robuste des demandes en trafic des flux à partir de mesures SNMP sur la charge des liens. Les résultats expérimentaux, aussi bien sur des trafics simulés que réels, montrent que le taux de congestion du réseau peut être significativement réduit par rapport à une configuration statique.Dans la même optique, nous nous intéressons également à l'optimisation des réseaux MPLS, qui permettent de gérer l'utilisation des ressources disponibles en affectant un chemin spécifique à chaque LSP. Nous proposons un algorithme inspiré de la théorie des jeux pour déterminer le placement des LSP optimisant un critère de performance non linéaire. Nous établissons la convergence de cet algorithme et obtenons des bornes sur son facteur d'approximation pour plusieurs fonctions de coût. L'intérêt principal de cette technique étant d'offrir des solutions de bonne qualité en des temps de calcul extrêmement réduits, nous étudions son utilisation pour la reconfiguration dynamique du placement des LSP.La dernière partie de cette thèse est consacrée à la conception et au développement d'une solution logicielle permettant le déploiement d'un réseau overlay auto-guérissant et auto-optimisant entre différentes plateformes de cloud computing. La solution est conçue pour ne nécessiter aucun changement des applications. En mesurant régulièrement la qualité des liens Internet entre les centres de données, elle permet de détecter rapidement la panne d'une route IP et de basculer le trafic sur un chemin de secours. Elle permet également de découvrir dynamiquement les chemins dans le réseau overlay qui optimisent une métrique de routage spécifique à l'application. Nous décrivons l'architecture et l'implémentation du système, ainsi que les expériences réalisées à la fois en émulation et sur une plateforme réelle composée de plusieurs centres de données situés dans différents pays. / The high variability of traffic has become one of the major problems faced by network infrastructure managers . Under these conditions, flow route optimization based solely on an average busy hour traffic matrix is no longer relevant. The work done in this thesis aims to design dynamic routing optimization methods, adapting in real time the routes used by the flows to the actual network traffic conditions.We first study the problem of OSPF weight optimization for intra-domain routing in IP networks, where the traffic is routed along shortest paths, according to links weights. We propose an online scheme to dynamically reconfigure the OSPF weights and therefore the routes used, to respond to observed traffic variations and reduce the network congestion rate. The proposed approach is based on robust estimation of flow traffic demands from SNMP measurements on links loads. Experimental results, both on simulated and real traffic data show that the network congestion rate can be significantly reduced in comparison to a static weight configuration.On the same idea, we are also interested in optimizing MPLS networks that manage the available resource utilization by assigning a specific path for each LSP. We propose an algorithm inspired by game theory to determine the LSP placement optimizing a nonlinear performance criterion. We establish the convergence of the algorithm and obtain bounds on its approximation factor for several cost functions. As the main advantage of this technique is to offer good quality solutions in extremely reduced computation times, we are studying its use for dynamic reconfiguration of the LSP placement.The last part of this thesis is devoted to the design and development of a software solution for the deployment of a self-healing and self-optimizing network overlay between different cloud platforms. The solution is designed such that no change is required for client applications. By regularly measuring the quality of Internet links between data centers, it can quickly detect an IP route failure and switch the traffic to a backup path. It also allows to dynamically discover the paths in the overlay network that optimize a routing metric specific to the application. We describe the system architecture and implementation, as well as the experiments in both emulation and real platform composed of several data centers located in different countries

京都大学 / 0048 / 新制・課程博士 / 博士(情報学) / 甲第19123号 / 情博第569号 / 新制||情||100(附属図書館) / 32074 / 京都大学大学院情報学研究科数理工学専攻 / (主査)教授 山下 信雄, 教授 中村 佳正, 教授 田中 利幸 / 学位規則第4条第1項該当 / Doctor of Informatics / Kyoto University / DFAM

[pt] Nesse trabalho, propomos o problema AdInvest, que modela o processo decisiório de alocação de investimento em marketing digital do ponto de vista do anunciante. Para o problema proposto, definimos um algoritmo chamado balGreedy, e provamos suas garantias para instâncias determísticas e estocásticas do AdInvest. Os teoremas provados garantem ao nosso algoritmo resultados de pior caso relativamente próximos ao OPT, em diversos tipos de instâncias levantadas ao decorrer do trabalho. Em especial, focamos nas instâncias que modelam o efeito de saturação das audiências, que se faz presente na dinâmica de anúncios online. Como mostrado nos experimentos computacionais, o algoritmo balGreedy se mostrou consistentemente eficiente em comparação com as políticas alternativas adotadas, tanto nas instâncias que foram geradas por simulação, quanto em instâncias reais obtidas a partir de dados de um anunciante do Facebook Ads. / [en] In this work, we propose the problem AdInvest, which models the decision-making process for allocating investment in digital marketing from the advertiser perspective. For the proposed problem, we define an algorithm called balGreedy, and we prove its guarantees in deterministic and stochastic instances of the AdInvest. The proven theorems assure to our algorithm worst-case results relatively close to OPT, in several types of instances raised during the work. In particular, we focus on the instances that model the audience saturation effect, which is present in the dynamics of online advertisements. As shown in the computational experiments, the balGreedy algorithm had been consistently efficient compared to the alternative policies adopted, both in the instances generated by simulation and in real instances built from the data of a certain Facebook Ads advertiser.