Magíster en Gestión de Operaciones / El objetivo principal de este trabajo es proporcionar un algoritmo que resuelve instancias de gran tamaño para problemas de juegos de seguridad de Stackelberg con un énfasis en reducir el número de recursos necesarios requeridos para calcular dicha solución. Para ello se utilizan los principios de generación de columnas para desarrollar un algoritmo que procede mediante la resolución de un problema más pequeño (menor número de restricciones). Entonces, de forma iterativa, añadimos restricciones hasta que el problema llega a las condiciones de parada definidas. Básicamente, partimos de un problema secundario del original con dos jugadores que juegan a la seguridad y cuentan con un espacio de estrategia limitado, ya que este considera sólo un número limitado de restricciones. Iterativamente, verificamos si algún jugador le gustaría cambiar su estrategia con el fin de incrementar sus utilidades, añadimos la estrategia candidata y resolvemos una vez más. Esto sugiere un método de descomposición que es capaz de estimar el conjunto mínimo de restricciones a tener en cuenta con el fin de encontrar también la solución óptima para el problema global. En el transcurso de nuestros estudios identificamos que el proceso de iteración no siempre encuentra la solución óptima para el problema global. Luego, proporcionamos un análisis y caracterización de la estructura de las funciones de utilidad para ambos jugadores con el fín comprender más la dinámica de los jugadores e identificar las situaciones en las que la solución óptima global efectivamente es encontrada. Más tarde, se presenta una implementación que incluye datos del mundo real a través de una red en el centro de Santiago, Chile. Las recompensas se calcularon teniendo en cuenta el promedio histórico robado en cada lugar y un valor estimado de la falta de voluntad de ir a la cárcel para efectos de los asaltantes. Finalmente, comparamos nuestro algoritmo con los demás ya la literatura en escenarios similares. Mostramos que nuestros métodos nos permiten ofrecer de manera eficiente soluciones razonables para los problemas de seguridad en tamaño del mundo real. Además comparamos nuestros resultados con los resultados utilizando la metodología estándar de resolución de problemas lineales y mostramos que se pueden reducir ampliamente la necesidad de recursos computacionales y en algunos casos, el tiempo de ejecución para llegar a la solución.

Ingeniero Civil Mecánico / Para el diseño de estructuras es indispensable conocer la fuerza que actúa sobre estas con el propósito de desarrollar mejores criterios de diseño, planes de mantención, evitar fallas catastróficas o prolongar la vida útil de las estructuras. Una forma indirecta de identificar las fuerzas que actúan sobre una estructura es mediante la medición de la respuesta dinámica de la estructura, la cual puede ser en forma de desplazamientos, velocidades, aceleración o deformaciones. Esto se conoce como el problema inverso. Dentro de los algoritmos de identificación de fuerzas más utilizados están los métodos en el dominio de las frecuencias y los métodos en el dominio del tiempo. Ambos métodos se traducen en resolver un problema de mínimos cuadrados que busca minimizar el error entre la fuerza estimada mediante el algoritmo y la fuerza aplicada. Sin embargo, resolver este problema lleva intrínseca la inversión de una matriz que muchas veces está mal acondicionada, lo que hace que la solución no sea única y/o sea inestable ante pequeñas variaciones de la respuesta dinámica. Además, muchos de estos métodos solo entregan la fuerza en los puntos de medición, por lo que no se tiene un conocimiento completo del comportamiento de la estructura. El objetivo del presente trabajo es desarrollar y validar un algoritmo de identificación de fuerzas dinámicas para una viga, aplicando un método de aproximación lineal. Donde una fuerza arbitraria es posible escribirla como una combinación lineal de fuerzas tipo impulso aplicadas en distintos tiempos. En primera instancia se realiza un modelo numérico de la viga en elementos finitos mediante el software Matlab, para luego realizar el algoritmo de identificación de fuerzas dinámicas y así validarlo en forma numérica y posteriormente en forma experimental. Se obtuvo que este algoritmo permite estimar la fuerza aplicada con bastante exactitud. Pudiendo calcular la fuerza aplicada en nodos donde no se mide la respuesta, por lo que no se requiere a priori una cantidad excesiva de sensores para tener buenas estimaciones. Además de no ser necesarias las propiedades de la viga en estudio para la determinación de la fuerza real aplicada en el análisis experimental. Sin embargo, para fuerzas con frecuencias de excitación cercanas a las frecuencias naturales de la viga, el algoritmo pierde precisión. Por otro lado, al disponer de una mayor cantidad de sensores midiendo la respuesta de la viga, el algoritmo disminuye los errores de estimación de la fuerza.

Doctor en Sistemas de Ingeniería / En esta tesis presentamos contribuciones algorítmicas y de modelación para Juegos de Stackelberg para problemas de gran tamaño. Juegos de Stackelberg es un tipo de juego en el que un jugador, llamado líder, utiliza una estrategia y luego el otro jugador, llamado seguidor, observa esta estrategia y juega una mejor respuesta. En el contexto de seguridad, el lider se le denomina defensor, y al seguidor se le denomina atacante. En el Capítulo 1, presentamos una situación en donde el defensor tiene que emparejar recursos para poder desarrollar labores de patrullaje. En este caso, el conjunto de estrategias puras es de tamaño exponencial. Presentamos una formulación en programación lineal entera mixta con un número polinomial de variables y un número exponencial de restricciones que pueden ser separadas en tiempo polinomial. Además, se diseñó un método de sampleo para recuperar estrategias implementables para el defensor. Por otra parte, mostramos un caso de estudio basado en el patrullaje fronterizo de Carabineros de Chile. Finalmente mostramos que nuestro modelo con el generación de cortes funciona considerablemente mejor que cualquier modelo en la literatura. En el Capítulo 2, se muestra una manera de escalar un algoritmo basado en Aprendizaje de M\'aquinas, realizando multiples capas de clusters de territorios en donde en cada cluster el algoritmo resuelve en tiempos razonables. En el Capítulo 3 se realiza un estudio sobre existencia de estrategias estacionarias que formen equilibrios de estrategias fuertes. Se detecta una familia de instancias en las cuales algoritmos de programación dinámica pueden encuentran el único equilibrio de Stackelberg fuerte. En este caso, se demuestra que Iteración de políticas y de valores convergen a los únicos valores de equilibrio. Se muestra vía contraejemplo que no siempre programación dinámica puede encontrar equilibrios de Stackelberg en estrategias estacionarias. Computacionalmente se encuentra que la estructura de juegos de seguridad presentara características que hace aplicable la teoría de operadores para encontrar equilibrios de Stackelberg. Finalmente se estudian formulaciones basadas en programación matemática para calcular equilibrios de Stackelberg. Finalmente, en el Capítulo 4 mostramos un juego dinámico, en donde un agente central tiene como objetivo la sobreexplotación de agua en el contexto agrícola, controlando los costos marginales de extracción que enfrentan los agricultores. Modelamos esta situación como un juego estocástico en donde se busca un equilibrio de Stackelberg en donde el líder es la agencia central, y los seguidores son los agricultores. Computacionalmente se encuentra que se pueden alcanzar mejores niveles de agua en el estado estacionario controlando los costos marginales a través de las tasas de descuento del líder, aunque los agricultures sean miopes. Finalmente, nosotros proponemos una formulación de programación robusta para incluir incertidumbre en nuestros modelos. / Este trabajo ha sido parcialmente financiado por CONICYT

Doctor en Ciencias de la Ingeniería, Mención Modelación Matemática / En esta tesis doctoral se estudian algoritmos para resolver problemas de optimización convexa con estructura separable, y problemas de equilibrio económico de Walras. Así, la tesis se divide en dos partes. La primera parte corresponde al estudio teórico y numérico de un método de direcciones alternantes de multiplicadores el cual usa un término proximal interior. La segunda parte está dedicada al estudio numérico de algoritmos de segundo orden para resolver problemas de maximización de utilidades que aparecen en problemas de equilibrio en economía. En el primer capítulo se hace una revisión de algunos métodos de descomposición basados en el Lagrangeano aumentado. Luego, se hace una revisión de la definición y propiedades de las distancias proximales generalizadas. En el segundo capítulo, se prueba la convergencia global del método propuesto bajo supuestos estándares. Este método es llamado Método de Direcciones Alternantes con Regularización Proximal Interior (RIPADM). En el tercer capítulo, se establece la convergencia global de una variante del método RIPADM la cual añade un factor de relajación a la regla de actualización del multiplicador de Lagrange. En el cuarto capítulo, se implementa computacionalmente en Matlab, el método RIPADM, el ADM original y el método proximal de multiplicadores (PMM) para resolver el problema LASSO restringido y un problema de máquinas de soporte vectorial. En la implementación computacional del método RIPADM se usa la distancia proximal Log-quad, y la distancia Kullback-Leibler. En el quinto capítulo, se describe el modelo de intercambio puro de Arrow-Debreau, y se hace una revisión de un método recientemente propuesto para resolver problemas de equilibrio económico de Walras. En el sexto capítulo, se implementa computacionalmente el método punto-interior primaldual (PDIPM) y el método gradiente proyectado con aceleración (AGPM) para resolver problemas de maximización de utilidades que aparecen en problemas de equilibrio en economía. / This thesis deals with algorithms for solving convex optimization problems with separable structure, and Walras economic equilibrium problems. So the thesis is divided into two parts. The first part corresponds to a theoretical and numerical study of an alternating direction method of multipliers which uses an inner proximal term. The second one is focused on numerical study of algorithms for solving utility maximization problems that arise in equilibrium problems in economic. The first chapter includes a review of some decomposition methods based on the augmented Lagrangian. Then, the definition and properties of generalized proximal distances are given. In the second chapter, the global convergence of the proposed method is proved. This method is called Alternating Direction Method with Interior Proximal Regularization (RIPADM). The third chapter contains the proof of the global convergence of a variant of the RIPADM method which adds a relaxation factor in the update rule of Lagrange multiplier. The fourth chapter corresponds to the computational implementation in Matlab of the RIPADM method, the original ADM and proximal method of multipliers (PMM), to solve the LASSO problem and a support vector machine problem. In the computational implementation of the RIPADM method it is used the Log-quad distance, and also is used the Kullback-Leibler distance which is a Bregman distance. The fifth chapter includes a description of the pure exchange model of Arrow-Debreau, and a review of a recently proposed method to solve Walras economic equilibrium problems. The sixth chapter corresponds to the computational implementation of primal-dual interiorpoint method (PDIPM) and the projected gradient method with acceleration (AGPM) for solving utility maximization problems that appear in Walras economic equilibrium problems.