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.

General

Un modelo en su forma estándar es la minimización de una función real $f$ en el espacio de los parámetros ${\vec {x}}\in P$, o en el subespacio definido por las restricciones $D$. (El problema de maximizar la función $g(x)$ es equivalente a minimizar una función $f(x)=(-1)\cdot g(x)$.)

En muchos problemas de optimización no linear, la función objetivo $f$ 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.

Aplicaciones

Algunos de los casos en los que se debe usar un enfoque de optimización global son:

• Predicción de la estructura de las proteínas (minimizar la energía/función de energía libre).
• Filogenética computacional (por ejemplo, minimizar el número de transformaciones de caracteres del árbol).
• Problema del viajante y el diseño de circuitos eléctricos (minimizar la longitud del camino).
• Ingeniería química (por ejemplo, Analizar la energía libre de Gibbs).
• Verificación de seguridad, ingeniería de seguridad (por ejemplo, de estructuras mecánicas, edificios).
• Análisis del caso peor
• Problemas matemáticos (por ejemplo, la Conjetura de Kepler).
• El punto de partida de numerosas simulaciones dinámicas moleculares que consisten en una optimización inicial de la energía del sistema a ser simulado.
• Calibración de los modelos de propagación de radio y otros modelos en la ciencia y en la ingeniería
• Ajuste de curvas como el análisis mínimo cuadrático y otras generalizaciones, como el ajuste de los datos de modelos experimentales, en la química, física, medicina, astronomía y otros.

Métodos deterministas

Las estrategias más usadas son:

Inner and outer approximation

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.

Cutting planes

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

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

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 álgebra

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.

Métodos estocásticos

Muchos algoritmos basados en Monte-Carlos existen:

Simulated annealing

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.

Método de muestreo directo de Monte-Carlo

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

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

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

Heurísticas y metaheurísticas

Otros acercamientos incluyen estrategias heurísticas para buscar en el espacio de búsqueda en una manera más inteligente, entre ellos:

• Algoritmos evolutivos(e.g., genetic algortihms y estrategias evolutivas)
• Swarm-based optimization algortihms(e.g., particle swarm optimization, multi-swarm optimization y ant colony optimization)
• Memetic algorithms, combinando estrategias de búsqueda local y global
• Reactive search optimization
• Differential evolution, un método que optimiza un problema mejorando la solución iterativamente teniendo en cuenta una medida de calidad.
• Graduated optimization, técnica que trata de resolver un problemas de optimización complejos, resolviendo primero una versión más simple del mismo y transformándolo progresivamente (mientras se optimiza) en un problema equivalente al problema de optimización original.​​​

Aproximaciones basadas en metodologías de superficies de respuesta

• IOSO Optimización indirecta basada en organización propia.
• Bayesian optimization, una estrategia de diseño sequencial para problemas de optimización global donde se asume la función como una caja negra usando estadística bayesiana.​

Software

1. Libres y de código abierto:

• OpenOpt

2. Comercial:

• LIONsolver
• TOMLAB for Matlab
• Optimus platform
• The NAG Numerical Library contains routines for both global and

local optimization.

• Demo global optimization software versions are available also for a

number of commercial software products.

• XTREME a single and

multiple objective optimization software for nonlinear optimization (GUI, Excel, C/C++ API and Python)

Véase también

• Optimización

Referencias

Deterministic global optimization:

• R. Horst, H. Tuy, Global Optimization: Deterministic Approaches,

Springer, 1996.

• R. Horst, P.M. Pardalos and N.V. Thoai, Introduction to Global

Optimization, Second Edition. Kluwer Academic Publishers, 2000.

• A.Neumaier, Complete

Search in Continuous Global Optimization and Constraint Satisfaction, pp. 271-369 in: Acta Numérica 2004 (A. Iserles, ed.), Cambridge University Press 2004.]

• M. Mongeau, H. Karsenty, V. Rouzé and J.-B. Hiriart-Urruty, Comparison

of public-domain software for black box global optimization.

Optimization Methods & Software 13(3), pp. 203–226, 2000.

• J.D. Pintér, Global Optimization in Action - Continuous and Lipschitz

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.

• L. Jaulin, M. Kieffer, O. Didrit, E. Walter (2001). Applied Interval

Analysis. Berlin: Springer.

• E.R. Hansen (1992), Global Optimization using Interval Analysis,

Marcel Dekker, New York.

• R.G. Strongin, Ya.D. Sergeyev (2000) Global optimization with

non-convex constraints: Sequential and parallel algorithms, Kluwer Academic Publishers, Dordrecht.

• Ya.D. Sergeyev, R.G. Strongin, D. Lera (2013) Introduction to global

optimization exploiting space-filling curves, Springer, NY.

For simulated annealing:

• S. Kirkpatrick, C.D. Gelatt, and M.P. Vecchi. Science,

220:671–680, 1983. For reactive search optimization:

• Roberto Battiti, M. Brunato and F. Mascia, Reactive Search and

Intelligent Optimization, Operations Research/Computer Science Interfaces Series, Vol. 45, Springer, November 2008. ISBN 978-0-387-09623-0 For stochastic methods:

• A. Zhigljavsky. Theory of Global Random

Search. Mathematics and its applications. Kluwer Academic Publishers. 1991.

• K. Hamacher. Adaptation in Stochastic Tunneling Global Optimization of

Complex Potential Energy Landscapes, Europhys.Lett. 74(6):944,

2006.

• K. Hamacher and W. Wenzel. The Scaling Behaviour of Stochastic

Minimization Algorithms in a Perfect Funnel Landscape. Phys. Rev. E,

59(1):938-941, 1999.

• W. Wenzel and K. Hamacher. A Stochastic tunneling approach for global

minimization. Phys. Rev. Lett., 82(15):3003-3007, 1999. For parallel tempering:

• U. H. E. Hansmann. Chem.Phys.Lett., 281:140, 1997.

For continuation methods:

• Zhijun Wu. The effective energy transformation scheme as a special

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:

• K. Hamacher. On Stochastic Global Optimization of one-dimensional

functions. Physica A 354:547-557, 2005.

Enlaces externos

• Página de A. Neumaier sobre optimización global
• Introducción a la optmización global por L. Liberti
• E-libro gratuito por Thomas Weise Archivado el 11 de septiembre de 2008 en Wayback Machine.

• Datos: Q25400955