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

29 Julio 2021 - Google Meet | UNC Estudiantes

Defensa de tesis para optar al grado de Doctora en Matemática | Tesista: Lic. Johanna Analiz FRAU

Tribunal Especial:

Dra. Ana Gabriela Martínez (Departamento de Matemática, UFPR - Brasil)

Dr. Andrés Alberto Barrea (FAMAF)

Dr. Juan Pablo Agnelli (FAMAF)

Lugar: enlace de meet

Resumen:

Existen actualmente muchas aplicaciones de problemas de optimización provenientes de la vida real donde las evaluaciones de la función objetivo (y las restricciones si las hubiera) son muy costosas o complejas computacionalmente, o bien la información disponible se origina a partir de datos experimentales y por lo tanto no existe una expresión explícita de tales funciones. Dado que este tipo de problemas no puede ser resuelto mediante métodos clásicos de optimización, es decir aquellos que involucran el cálculo de derivadas, hace algunas décadas comenzaron a estudiarse y desarrollarse métodos de Optimización sin derivadas. Básicamente, estos nuevos métodos y algoritmos, principalmente propuestos para optimización local con y sin restricciones, están basados en técnicas relacionadas con exploración en entornos y movimientos hacia nuevos puntos que muestren alguna mejora en la evaluación de la función. En esta tesis doctoral presentamos y desarrollamos dos nuevos modelos de optimización sin derivadas. En primer lugar, proponemos un nuevo método para optimización local 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. Asimismo, 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. Las mismas fueron inicialmente formuladas para resolver problemas de minimización sin restricciones y sistemas de ecuaciones no lineales, con y sin derivadas, y fueron adaptadas al problema de minimización con restricciones de cajas que resuelve el algoritmo nmps. La segunda parte de esta tesis se encuentra enmarcada dentro de los métodos Lipschitzianos para optimización global propuestos inicialmente por Jones et al. y enmarcados dentro de la familia de algoritmos DIRECT. Por un lado, proponemos un algoritmo que utiliza una búsqueda local sin derivadas (nmps) dentro de un algoritmo de optimización global (BIRECT) para resolver un problema de optimización con restricciones de 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 que combina la estrategia de BIRECT junto con las ideas propuestas por Jones al adaptar DIRECT al problema con restricciones generales. El nuevo algoritmo propuesto hereda las propiedades de convergencia de los algoritmos de la familia DIRECT, las cuales se basan fuertemente en argumentos de densidad. Debido a la complejidad algorítmica de este problema de optimización global con restricciones y sin derivadas, esta parte del trabajo se caracteriza por un importante desarrollo computacional acompañado de un análisis detallado de la performance del nuevo algoritmo.