Convergencia y optimización global en programación no lineal. Teoría y algoritmos

Abstract

A variety of decision-making problems that arise in areas as diverse as science, engineering, economics, among others, can be modeled mathematically as a constrained optimization problems. When we want to optimize and model real situations arise mathematical models using functions of different types, linear and nonlinear. Under conditions of convexity for functions there is a robust theory that guarantees the global solution of the problems. Most of engineering and applied science problems of interest involve optimization models with non-convex functions, which are complex to solve due to the existence of multiple local solutions. Convex optimization techniques applied to these non-convex problems do not guarantee the global optimum of the problem, so it is a matter of study, known as global optimization. In this thesis, the general characteristics of the deterministic algorithm Branch and bound (Branch and Bound) developed for non-convex models, studying their problems in some of the techniques proposed in the area of global optimization. We carried out a reformulation of the method "Improve and Branch" developed by Marcovecchio, Bergamini and Aguirre, deterministic algorithm and optimize branch type to be deployed to reduce levels and restrictions to reduce the feasible region.

Una gran variedad de problemas de toma de decisión que surgen de áreas tan diversas como las ciencias, ingeniería, economía, administración entre otras, pueden ser modelados matemáticamente como problemas de optimización restringidos. Cuando queremos optimizar y modelar situaciones reales, surgen modelos matemáticos formulados mediante funciones de diversos tipos, lineales y no lineales. Bajo condiciones de convexidad para las funciones existe una teoría robusta que garantiza la solución global de los problemas. La mayoría de los problemas de ingeniería y ciencias aplicadas involucran modelos de optimización con funciones no convexas, resultando su resolución compleja debido a la existencia de óptimos locales múltiples. Las técnicas de optimización convexa aplicadas a estos problemas no convexos no garantizan el óptimo global del problema, por lo que son motivo de estudio, conocido como optimización global. En esta tesis se estudian las características generales de los algoritmos determinísticos de Ramificación y Acotamiento (Branch and Bound) desarrollados para modelos no convexos, estudiando su problemática en algunas de las técnicas propuestas en el área de optimización global. Finalmente se realiza una reformulación del método “Improve and Branch” desarrollado por Marcovecchio, Bergamini y Aguirre, algoritmo determinístico de tipo ramificar y optimizar al que se le implementan reducción de cotas y restricciones de reducción de la región factible.