Métodos computacionales para optimización local y global sin derivadas

Abstract

En esta tesis doctoral presentamos y desarrollamos dos nuevos modelos de optimización sin derivadas. En primer lugar, proponemos un nuevo método de búsqueda de patrones para optimización local, denominado algoritmo nmps, con restricciones de cotas en las variables el cual utiliza una técnica de búsqueda lineal no monótona en la elección de los nuevos iterados. El nuevo método, cuyo algoritmo es denominado nmps, pertenece a la familia de los métodos de búsqueda de patrones y se demuestran resultados de convergencia global de primer orden. Esta nueva propuesta algorítmica fue acompañada por un extenso estudio numérico en el cual se utilizaron diferentes estrategias de búsqueda lineal no monótonas. La segunda propuesta de esta tesis se encuentra enmarcada dentro de los métodos Lipschitzianos para optimización global. Por un lado, incorporamos el algoritmo nmps (optimización local) dentro del algoritmo BIRECT (optimización global) en la resolución de un problema de optimización con restricciones de cajas o cotas en las variables. Esta combinación de estrategias tuvo por objetivo determinar, mediante un estudio numérico, si la integración de un algoritmo de búsqueda local, del tipo búsqueda de patrones, dentro de un algoritmo de búsqueda global mejora la obtención del punto óptimo al explorar entornos de los iterados. Por otro lado, como última contribución, proponemos e implementamos un nuevo método para problemas de optimización global con restricciones generales al adaptar el algoritmo DIRECT al problema con restricciones generales. El nuevo algoritmo hereda las propiedades de convergencia de los algoritmos de la familia DIRECT, las cuales se basan fuertemente en argumentos de densidad.

In this doctoral thesis, we present and develop two new Derivative-free optimization models. First, we propose a new method for bound constrained local optimization that uses a nonmonotone line-search technique for choosing a new iterate. The new method, whose algorithm is named nmps, belongs to pattern search family methods and global first order convergence results are proven. Besides, this new algorithmic proposal was accompanied by an extensive numerical study in which different nonmonotone line-search strategies were implemented. During the second part of this thesis, we address lipschitzian methods for global optimization. On one side, we incorporate nmps algorithm (local optimization) inside BIRECT algorithm (global optimization) for solving a bound constrained optimization problem. The main goal of this task was to determine if the integration of a local search algorithm (of type pattern search) into a global search algorithm would improve the optimal point found. On the other hand, as a last contribution, we propose and implement a new method for solving global optimization problems with general constraints by adapting DIRECT algorithm to general constraints. The new algorithm inherits convergence properties from DIRECT family algorithms which are strongly based on density arguments.