Optimización global
Optimización Global es una rama de la matemática aplicada y el análisis numérico que se ocupa de la optimización de una función o un conjunto de funciones de acuerdo a diferentes criterios.
Por lo general, un conjunto de cotas y restricciones más generales también se encuentra presente, siendo las variables de decisión optimizadas de acuerdo a las restricciones.
Un modelo en su forma estándar es la minimización de una función real en el espacio de los parámetros , o en el subespacio definido por las restricciones . (El problema de maximizar la función es equivalente a minimizar una función .)
En muchos problemas de optimización no linear, la función objetivo tiene un gran número de mínimos y máximos locales, encontrar un óptimo local es una tarea sencilla, usando métodos clásicos de optimización local.En estos caso encontrar un mínimo o un máximo global es una tarea de mayor complejidad, pues los métodos analíticos no se pueden utilizar en la gran mayoría de los casos y las estrategias numéricas traen consigo un número grande de problemas.
Algunos de los casos en los que se debe usar un enfoque de optimización global son:
Las estrategias más usadas son:
En ambas estrategias, el conjunto sobre el que las funciones va a ser optimizadas es un poliedro. En la aproximación interior el poliedro es contenido en el conjunto, mientras en la aproximación exterior el poliedro contiene al conjunto.
El cutting planes es un término global para los métodos de optimización que iterativamente refinan un conjunto factible o la función objetivo añadiéndole desigualdades lineales, llamadas cortes. Estos procedimientos son muy utilizados para encontrar soluciones enteras y soluciones enteras mixtas de problemas de programación lineal, así como resolver problemas generales de optimización convexos, no necesariamente diferenciable function by means of linear inequalities, termed cuts. El uso de planos cortantes para resolver problemas de optimización lineal mixtos fue introducido por Ralph E. Gomory and Václav Chvátal.
Branch and bound es un paradigma de los algoritmos diseñados para la optimización de problemas discretos y combinatorios. Un algoritmo de ramificación y acotación consiste en la enumeración sistemática de soluciones candidatas del espacio de búsqueda.El algoritmo explora las ramas del árbol, que representan un subconjunto de las soluciones. Antes de las soluciones candidatas de la rama, la rama es revisada contra las diferentes acotaciones de la solución óptima, y descartadas si no pueden producir una mejor solución que la mejor encontrada hasta ahora.
Interval arithmetic es un método desarrollado por los matemáticos desde los años 50 del siglo pasado como un enfoque para añadir cotas en los errores de redondeo y la medición de errores en problemas de matemática computacional en el desarrollo de métodos numéricos que lleven a resultados confiables.La aritmética de intervalos ayuda a encontrar soluciones confiables a ecuaciones y problemas de optimización.
Real algebra es la parte del álgebra que es relevante a la geometría real algebraica y semi algebraica. En su mayoría le concierne al estudio de los campos ordenados o de los anillos ordenados, y su aplicación al estudio de polinomios positivos y la suma de los polinomios al cuadrado. Puede ser usado en la optimización convexa.
Muchos algoritmos basados en Monte-Carlos existen:
Simulated annealing (SA)' es una metaheurística probabilística para la optimización global de problemas de encontrar una buena aproximación del optimo global de una función dada en un espacio de búsqueda grande. Es a menudo usado si el espacio de búsqueda es discreto. Para ciertos problemas simulated annealing es más eficiente que la enumeración exhaustiva, poniendo que el objetivo es encontrar una solución aceptable en un espacio de tiempo pequeño más que encontrar la mejor solución posible.
En este método, simulaciones aleatorias son utilizadas para utilizar soluciones aproximadas Ejemplo: El problema del viajante es uno de los problemas de optimización más famosos, cuyo objetivo es encontrar el camino óptimo a seguir que cumpla con que se recorrió la menor distancia posible. Asumamos que en vez de minimizar la distancia total del viajero para visitar cada ciudad, queremos minimizar el tiempo necesitado para llegar a cada destino. Esto va más allá de la optimización convencional. Como resultado para determinar este nuevo camino optimal querríamos usar simulación-optimización para entender el rango de tiempos potenciales que podría tomar ir de un punto a otro y entonces optimizar nuestras decisiones de viaje para identificar el mejor camino a seguir tomando en cuenta la incertidumbre.
Stochastic tunneling (STUN) es un acercamiento a la optimización global basado en el método de muestreo de Monte-Carlo de la función objetivo a ser minimizada en el cual la función es transformada no linealmente para permitir un fácil tunneling entre las regiones que contienen mínimo de función. Un tunneling más sencillo permite una exploración más rápida del espacio muestral así como una convergencia más rápida hacia buena solución.
Parallel tempering es método de simulación dirigido a mejorar las propiedades dinámicas del método de Monte Carlo de simulación de sistemas físicos. Esencialmente, se corren N copias del sistema, inicializados de manera aleatoria a diferentes temperaturas.La idea de este método es hacer disponibles las configuraciones a altas temperaturas a las simulaciones de bajas temperaturas y viceversa. Esto resulta en un conjunto robusto el cual es posible muestrear tanto configuraciones de bajas y altas temperaturas
Otros acercamientos incluyen estrategias heurísticas para buscar en el espacio de búsqueda en una manera más inteligente, entre ellos:
1. Libres y de código abierto:
2. Comercial:
local optimization.
number of commercial software products.
multiple objective optimization software for nonlinear optimization (GUI, Excel, C/C++ API and Python)
Deterministic global optimization:
Springer, 1996.
Optimization, Second Edition. Kluwer Academic Publishers, 2000.
Search in Continuous Global Optimization and Constraint Satisfaction, pp. 271-369 in: Acta Numérica 2004 (A. Iserles, ed.), Cambridge University Press 2004.]
Optimization Methods & Software 13(3), pp. 203–226, 2000.
Optimization: Algorithms, Implementations and Applications. Kluwer Academic Publishers, Dordrecht, 1996. Now distributed by Springer Science and Business Media, New York. This book also discusses stochastic global optimization methods.
Analysis. Berlin: Springer.
Marcel Dekker, New York.
non-convex constraints: Sequential and parallel algorithms, Kluwer Academic Publishers, Dordrecht.
optimization exploiting space-filling curves, Springer, NY.
For simulated annealing:
220:671–680, 1983. For reactive search optimization:
Intelligent Optimization, Operations Research/Computer Science Interfaces Series, Vol. 45, Springer, November 2008. ISBN 978-0-387-09623-0 For stochastic methods:
Search. Mathematics and its applications. Kluwer Academic Publishers. 1991.
2006.
Minimization Algorithms in a Perfect Funnel Landscape. Phys. Rev. E,
minimization. Phys. Rev. Lett., 82(15):3003-3007, 1999. For parallel tempering:
For continuation methods:
continuation approach to global optimization with application to molecular conformation. Technical Report, Argonne National Lab., IL (United States), November 1996. For general considerations on the dimensionality of the domain of definition of the objective function:
functions. Physica A 354:547-557, 2005.