Optimización global - Global optimization

La optimización global es una rama de las matemáticas aplicadas y el análisis numérico que intenta encontrar los mínimos o máximos globales de una función o un conjunto de funciones en un conjunto dado. Por lo general, se describe como un problema de minimización porque la maximización de la función de valor real es equivalente a la minimización de la función . ${\ Displaystyle g (x)}$${\ Displaystyle f (x): = (- 1) \ cdot g (x)}$

Dada una función continua posiblemente no lineal y no convexa con los mínimos globales y el conjunto de todos los minimizadores globales en , el problema de minimización estándar se puede dar como ${\ Displaystyle f: \ Omega \ subconjunto \ mathbb {R} ^ {n} \ to \ mathbb {R}}$${\ Displaystyle f ^ {*}}$${\ Displaystyle X ^ {*}}$${\ Displaystyle \ Omega}$

${\ Displaystyle \ min _ {x \ in \ Omega} f (x),}$

es decir, encontrar un minimizador global en ; donde es un conjunto compacto (no necesariamente convexo) definido por desigualdades . ${\ Displaystyle f ^ {*}}$${\ Displaystyle X ^ {*}}$${\ Displaystyle \ Omega}$${\ Displaystyle g_ {i} (x) \ geqslant 0, i = 1, \ ldots, r}$

La optimización global se distingue de la optimización local por su enfoque en encontrar el mínimo o máximo sobre el conjunto dado, en lugar de encontrar mínimos o máximos locales . Encontrar un mínimo local arbitrario es relativamente sencillo mediante el uso de métodos clásicos de optimización local . Encontrar el mínimo global de una función es mucho más difícil: los métodos analíticos con frecuencia no son aplicables y el uso de estrategias de solución numérica a menudo conduce a desafíos muy difíciles.

Teoría general

Un enfoque reciente del problema de la optimización global es a través de la distribución mínima . En este trabajo, se ha establecido estrictamente una relación entre cualquier función continua en un conjunto compacto y sus mínimos globales . Como caso típico, se sigue que ${\ Displaystyle f}$${\ Displaystyle \ Omega \ subconjunto \ mathbb {R} ^ {n}}$${\ Displaystyle f ^ {*}}$

${\ Displaystyle \ lim _ {k \ to \ infty} \ int _ {\ Omega} f (x) m ^ {(k)} (x) \, \ mathrm {d} x = f ^ {*}, ~ ~ {\ textrm {donde}} ~~ m ^ {(k)} (x) = {\ frac {e ^ {- kf (x)}} {\ int _ {\ Omega} e ^ {- kf (x )} \, \ mathrm {d} x}};}$

mientras tanto,

${\ Displaystyle \ lim _ {k \ to \ infty} m ^ {(k)} (x) = \ left \ {{\ begin {array} {cl} {\ frac {1} {\ mu (X ^ { *})}}, & x \ in X ^ {*}, \\ 0, & x \ in \ Omega -X ^ {*}, \ end {array}} \ right.}$

donde es la medida de Lebesgue -dimensional del conjunto de minimizadores . Y si no es una constante , la monótona relación ${\ Displaystyle \ mu (X ^ {*})}$${\ Displaystyle n}$${\ Displaystyle X ^ {*} \ in \ Omega}$${\ Displaystyle f}$${\ Displaystyle \ Omega}$

${\ Displaystyle \ int _ {\ Omega} f (x) m ^ {(k)} (x) \, \ mathrm {d} x> \ int _ {\ Omega} f (x) m ^ {(k + \ Delta k)} (x) \, \ mathrm {d} x> f ^ {*}}$

vale para todos y , lo que implica una serie de relaciones monótonas de contención, y una de ellas es, por ejemplo, ${\ Displaystyle k \ in \ mathbb {R}}$${\ Displaystyle \ Delta k> 0}$

${\ Displaystyle \ Omega \ supset D_ {f} ^ {(k)} \ supset D_ {f} ^ {(k + \ Delta k)} \ supset X ^ {*}, {\ text {donde}} D_ {f } ^ {(k)} = \ left \ {x \ in \ Omega: f (x) \ leqslant \ int _ {\ Omega} f (t) m ^ {(k)} (t) \, \ mathrm { d} t \ right \}.}$

Y definimos una distribución mínima como un límite débil tal que la identidad ${\ Displaystyle m_ {f, \ Omega}}$

${\ Displaystyle \ int _ {\ Omega} m_ {f, \ Omega} (x) \ varphi (x) \, \ mathrm {d} x = \ lim _ {k \ to \ infty} \ int _ {\ Omega } m ^ {(k)} (x) \ varphi (x) \, \ mathrm {d} x}$

se sostiene para cada función suave con soporte compacto en . Aquí hay dos propiedades inmediatas de : ${\ Displaystyle \ varphi}$${\ Displaystyle \ Omega}$${\ Displaystyle m_ {f, \ Omega}}$

(1) satisface la identidad .${\ Displaystyle m_ {f, \ Omega}}$${\ Displaystyle \ int _ {\ Omega} m_ {f, \ Omega} (x) \, \ mathrm {d} x = 1}$

(2) Si es continuo , entonces .${\ Displaystyle f}$${\ Displaystyle \ Omega}$${\ Displaystyle f ^ {*} = \ int _ {\ Omega} f (x) m_ {f, \ Omega} (x) \, \ mathrm {d} x}$

A modo de comparación, la conocida relación entre cualquier función convexa diferenciable y sus mínimos está estrictamente establecida por el gradiente. Si es diferenciable en un conjunto convexo , entonces es convexo si y solo si ${\ Displaystyle f}$${\ Displaystyle D}$${\ Displaystyle f}$

${\ Displaystyle f (y) \ geqslant f (x) + \ nabla f (x) (yx), ~~ \ forall x, y \ in D;}$

por lo tanto, implica que vale para todos , es decir, es un minimizador global de on . ${\ Displaystyle \ nabla f (x ^ {*}) = 0}$${\ Displaystyle f (y) \ geqslant f (x ^ {*})}$${\ Displaystyle y \ in D}$${\ Displaystyle x ^ {*}}$${\ Displaystyle f}$${\ Displaystyle D}$

Aplicaciones

Los ejemplos típicos de aplicaciones de optimización global incluyen:

• Predicción de la estructura de la proteína (minimiza la función de energía / energía libre)
• Filogenética computacional (por ejemplo, minimizar el número de transformaciones de caracteres en el árbol)
• Problema del vendedor ambulante y diseño del circuito eléctrico (minimice la longitud del camino)
• Ingeniería química (p. Ej., Análisis de la energía de Gibbs )
• Verificación de seguridad , ingeniería de seguridad (por ejemplo, de estructuras mecánicas, edificios)
• Análisis del peor de los casos
• Problemas matemáticos (p. Ej., La conjetura de Kepler )
• Problemas de empaquetado de objetos (diseño de configuración)
• El punto de partida de varias simulaciones de dinámica molecular consiste en una optimización inicial de la energía del sistema a simular.
• Girar vasos
• Calibración de modelos de propagación de radio y de muchos otros modelos en ciencias e ingeniería.
• Ajuste de curvas como análisis de mínimos cuadrados no lineales y otras generalizaciones, utilizado para ajustar los parámetros del modelo a datos experimentales en química, física, biología, economía, finanzas, medicina, astronomía, ingeniería.
• Planificación de la radioterapia IMRT

Métodos deterministas

Las estrategias exactas generales más exitosas son:

Aproximación interior y exterior

En ambas estrategias, el conjunto sobre el que se optimizará una función se aproxima mediante poliedros. En aproximación interna, los poliedros están contenidos en el conjunto, mientras que en aproximación externa, los poliedros contienen el conjunto.

Métodos de plano de corte

El método del plano de corte es un término general para los métodos de optimización que refinan iterativamente un conjunto factible o una función objetivo por medio de desigualdades lineales, denominadas cortes . Estos procedimientos se utilizan popularmente para encontrar soluciones de números enteros a problemas de programación lineal de números enteros mixtos (MILP), así como para resolver problemas generales de optimización convexa , no necesariamente diferenciables . Ralph E. Gomory y Václav Chvátal introdujeron el uso de planos de corte para resolver MILP .

Métodos de ramificación y vinculación

Branch and bound ( BB o B&B ) es un paradigma de diseño de algoritmos para problemas de optimización discretos y combinatorios . Un algoritmo de ramificación y acotación consiste en una enumeración sistemática de soluciones candidatas mediante la búsqueda en el espacio de estados : se piensa que el conjunto de soluciones candidatas forma un árbol enraizado con el conjunto completo en la raíz. El algoritmo explora las ramas de este árbol, que representan subconjuntos del conjunto de soluciones. Antes de enumerar las soluciones candidatas de una rama, la rama se compara con los límites estimados superior e inferior de la solución óptima y se descarta si no puede producir una solución mejor que la mejor encontrada hasta ahora por el algoritmo.

Métodos de intervalo

La aritmética de intervalos , la matemática de intervalos , el análisis de intervalos o el cálculo de intervalos es un método desarrollado por matemáticos desde las décadas de 1950 y 1960 como un enfoque para poner límites a los errores de redondeo y de medición en el cálculo matemático y, por lo tanto, desarrollar métodos numéricos que produzcan resultados confiables. La aritmética de intervalos ayuda a encontrar soluciones fiables y garantizadas para ecuaciones y problemas de optimización.

Métodos basados ​​en geometría algebraica real

El álgebra real es la parte del álgebra que es relevante para la geometría algebraica (y semialgebraica) real. Se ocupa principalmente del estudio de campos ordenados y anillos ordenados (en particular campos cerrados reales ) y sus aplicaciones al estudio de polinomios positivos y sumas de cuadrados de polinomios . Se puede utilizar en optimización convexa.

Métodos estocásticos

Existen varios algoritmos basados ​​en Monte-Carlo, exactos o inexactos:

Muestreo directo de Montecarlo

En este método, se utilizan simulaciones aleatorias para encontrar una solución aproximada.

Ejemplo: el problema del viajante de comercio es lo que se denomina un problema de optimización convencional. Es decir, todos los hechos (distancias entre cada punto de destino) necesarios para determinar la ruta óptima a seguir se conocen con certeza y el objetivo es recorrer las posibles opciones de viaje para llegar a la que tenga la distancia total más baja. Sin embargo, supongamos que en lugar de querer minimizar la distancia total recorrida para visitar cada destino deseado, queríamos minimizar el tiempo total necesario para llegar a cada destino. Esto va más allá de la optimización convencional, ya que el tiempo de viaje es intrínsecamente incierto (atascos, hora del día, etc.). Como resultado, para determinar nuestra ruta óptima, querríamos usar simulación - optimización para comprender primero el rango de tiempos potenciales que podría tomar para ir de un punto a otro (representado por una distribución de probabilidad en este caso en lugar de una distancia específica). y luego optimizar nuestras decisiones de viaje para identificar el mejor camino a seguir teniendo en cuenta esa incertidumbre.

Túneles estocásticos

La tunelización estocástica (STUN) es un enfoque de optimización global basado en el método de Monte Carlo : el muestreo de la función se minimiza objetivamente en el que la función se transforma de forma no lineal para permitir una tunelización más fácil entre regiones que contienen mínimos de función. La construcción de túneles más sencilla permite una exploración más rápida del espacio muestral y una convergencia más rápida hacia una buena solución.

Templado paralelo

El templado paralelo , también conocido como muestreo MCMC de intercambio de réplicas , es un método de simulación destinado a mejorar las propiedades dinámicas de las simulaciones de sistemas físicos del método Monte Carlo , y de los métodos de muestreo de la cadena de Markov Monte Carlo (MCMC) en general. El método de intercambio de réplicas fue ideado originalmente por Swendsen, luego ampliado por Geyer y desarrollado más tarde, entre otros, por Giorgio Parisi . Sugita y Okamoto formularon una versión de dinámica molecular del templado paralelo: esto generalmente se conoce como dinámica molecular de intercambio de réplicas o REMD. .

Esencialmente, se ejecutan N copias del sistema, inicializadas aleatoriamente, a diferentes temperaturas. Luego, según el criterio de Metropolis, se intercambian configuraciones a diferentes temperaturas. La idea de este método es hacer que las configuraciones a altas temperaturas estén disponibles para las simulaciones a bajas temperaturas y viceversa. Esto da como resultado un conjunto muy robusto que puede muestrear configuraciones de baja y alta energía. De esta forma, las propiedades termodinámicas como el calor específico, que en general no se calcula bien en el conjunto canónico, se pueden calcular con gran precisión.

Heurística y metaheurística

Página principal: Metaheurística

Otros enfoques incluyen estrategias heurísticas para buscar el espacio de búsqueda de una manera más o menos inteligente, que incluyen:

• Optimización de colonias de hormigas (ACO)
• Recocido simulado , una metaheurística probabilística genérica
• Búsqueda tabú , una extensión de la búsqueda local capaz de escapar de los mínimos locales
• Algoritmos evolutivos (por ejemplo, algoritmos genéticos y estrategias de evolución )
• Evolución diferencial , un método que optimiza un problema al tratar iterativamente de mejorar una solución candidata con respecto a una determinada medida de calidad.
• Algoritmos de optimización basados ​​en enjambres (p. Ej., Optimización de enjambres de partículas , optimización cognitiva social , optimización de enjambres múltiples y optimización de colonias de hormigas )
• Algoritmos meméticos , que combinan estrategias de búsqueda globales y locales.
• Optimización de búsqueda reactiva (es decir, integración de técnicas de aprendizaje automático sub-simbólicas en heurísticas de búsqueda)
• Optimización graduada , una técnica que intenta resolver un problema de optimización difícil resolviendo inicialmente un problema muy simplificado y transformando progresivamente ese problema (mientras se optimiza) hasta que sea equivalente al problema de optimización difícil.

Enfoques basados ​​en la metodología de superficie de respuesta

• Optimización indirecta de IOSO basada en la autoorganización
• Optimización bayesiana , una estrategia de diseño secuencial para la optimización global de funciones de caja negra utilizando estadísticas bayesianas

Ver también

• Optimización global determinista
• Optimización de diseño multidisciplinar
• Optimización multiobjetivo
• Optimización (matemáticas)

Notas al pie

Referencias

enlaces externos

• A. Página de Neumaier sobre optimización global
• Introducción a la optimización global por L. Liberti
• Libro electrónico gratuito de Thomas Weise