Ponce López, Diego2024-12-202024-12-202024-06-04Gómez Toscano, L. (2024). Optimización online. (Trabajo Fin de Grado Inédito). Universidad de Sevilla, Sevilla.https://hdl.handle.net/11441/166055La Investigaci´on Operativa es una ciencia que estudia m´etodos anal´ıticos y aplicados para tomar decisiones ´optimas sobre un problema. Sin embargo, hay muchas situaciones de la vida real en las que estas decisiones deben tomarse bajo incertidumbre y esas elecciones afectar´an a estados futuros. Para tomar una buena decisi´on bas´andose solo en datos pasados y actuales, se han estudiado ampliamente diferentes t´ecnicas como los procesos de decisi´on de Markov o la optimizaci´on estoc´astica. No obstante, estos enfoques suponen alg´un modelo probabil´ıstico del futuro para resolver el problema. Por otro lado, en la optimizaci´on robusta, la incertidumbre se caracteriza por su pertenencia a conjuntos, en lugar de distribuciones. En este trabajo exploramos otro enfoque: la optimizaci´on online. Esta metodolog´ıa, popularizada a finales del siglo pasado en inform´atica, sienta las bases del an´alisis competitivo, que nos permite medir la calidad de una estrategia o pol´ıtica de decisi´on. La idea principal es comparar la evaluaci´on de una estrategia teniendo informaci´on incompleta sobre el futuro (online) con su versi´on cl´asica de optimizaci´on, donde se asume informaci´on completa (offline). El documento est´a estructurado de forma que se introducen los conceptos de optimizaci´on online de manera formal utilizando ejemplos para su comprensi´on. En primer lugar, se explican otras t´ecnicas que resuelven problemas con incertidumbre para que el lector tenga una visi´on completa y comprenda mejor las caracter´ısticas de la optimizaci´on online. En segundo lugar, se hacen definiciones formales de optimizaci´on offline y online para luego trabajar con el concepto de ratio competitivo. En el resto del documento, se analiza la competitividad te´oricamente desde problemas m´as simples hasta m´as complejos. Esto nos permite introducir conceptos como el ratio competitivo (estricto) de un algoritmo o problema, adversario, m´etodo de funci´on potencial o m´etodo del promedio. Los problemas cl´asicos que utilizamos como ejemplos son: el problema del alquiler de esqu´ıs como un primer contacto con la notaci´on de la optimizaci´on online; el problema de paginaci´on para ilustrar c´omo demostrar resultados de competitividad y desarrollar un an´alisis computacional emp´ırico que nos permita una mejor comprensi´on de los ratios competitivos en la pr´actica; el problema de actualizaci´on de listas que es un problema m´as complejo, por lo que aprovechamos para introducir las ideas del m´etodo de funci´on potencial y el promedio para estudiar te´oricamente su competitividad; finalizamos con el problema de k-servidores y algunas de sus extensiones con el fin de dar al lector una visi´on general de problemas de optimizaci´on online m´as realistas.Operations Research is a mathematical science that studies analytical and application methods to optimally make decisions on a problem. However, there are many real-life situations where these decisions have to be made under incomplete information besides those choices affect following states. In order to make a good decision based only in the past and the current data, different techniques as Markov decision processes or stochastic optimization has been widely studied. Nevertheless, these approaches assume some probabilistic model of the future to solve the problem. On the other hand, in robust optimization, uncertainty is characterized by set membership, rather than distributions. In this dissertation, we explore another approach: online optimization. This methodology, popularized at the end of the past century in computer science, lays the foundations of competitive analysis which lets us measure the quality of a decision strategy or policy. The main idea is to compare the evaluation of a strategy having incomplete information about the future (online) with its classical optimization version where complete information is assumed (offline). The document is structured to introduce online optimization concepts formally using examples to clarify them. Firstly, other techniques that solve problems with incomplete information are explained so the reader has a complete picture to better understand online optimization features. Secondly, formal definitions of offline and online optimization are made to later work with the concept of competitive ratio. In the rest of the document, competitiveness is analyzed theoretically from easier to more difficult problems. This lets us introduce concepts such as (strictly) competitive ratio of an algorithm or a problem, adversary, potential function method, or averaging method. The classic problems that we use as examples are: the ski rental problem as a first contact with online optimization notation; the paging problem to illustrate how to proofs competitiveness results and to develop an empirical computational analysis which let us better understanding about competitive ratios in practice; the list update problem is a more complex problem so we take advantage to introduce the ideas of potential function method and averaging to theoretically study its competitiveness; we finish with the k-server problem and some of its extensions in order to give the reader an overview of more realistic online optimization problems.application/pdfspaAttribution-NonCommercial-NoDerivatives 4.0 Internationalhttp://creativecommons.org/licenses/by-nc-nd/4.0/info:eu-repo/semantics/bachelorThesisinfo:eu-repo/semantics/openAccess