Optimización global

Optimización mundial es una rama de matemáticas aplicadas y análisis numérico que intenta encontrar el minima global o maxima de una función o un conjunto de funciones en un conjunto dado. Se describe generalmente como un problema de minimización porque la maximización de la función de valor real ${displaystyle g(x)}$ es equivalente a la minimización de la función ${displaystyle f(x):=(-1)cdot g(x)}$.

Dada una posible función continua no lineal y no convexa ${displaystyle f: Omega subset mathbb {R} a mathbb {R}$ con la minima global ${displaystyle f^{*}$ y el conjunto de todos los minimizadores globales ${displaystyle X^{*}$ dentro ${displaystyle Omega }$, el problema de minimización estándar se puede dar como

${displaystyle min _{xin Omega }f(x),}$

es decir, encontrar ${displaystyle f^{*}$ y un minimizador global en ${displaystyle X^{*}$; dónde ${displaystyle Omega }$ es un (no necesariamente convexo) compacto definido por las desigualdades ${displaystyle g_{i}(x)geqslant 0,i=1,ldotsr}$.

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 utilizando 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 frecuentemente no son aplicables y el uso de estrategias de solución numérica a menudo conduce a desafíos muy difíciles.

Aplicaciones

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

• Predicción de la estructura de proteínas (minimizar la función energética/gratuita)
• Filogenética computacional (por ejemplo, minimizar el número de transformaciones de caracteres en el árbol)
• Problema de viaje del vendedor y diseño de circuito eléctrico (minimice la longitud de la ruta)
• Ingeniería química (por ejemplo, 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 peor de casos
• Problemas matemáticos (por ejemplo, la conjetura de Kepler)
• Problemas de empaquetado de objetos (diseño de configuración)
• El punto de partida de varias simulaciones de dinámicas moleculares consiste en una optimización inicial de la energía del sistema a simular.
• Gafas de giro
• Calibración de modelos de propagación de radio y de muchos otros modelos en ciencias e ingeniería
• Fijación de curvas como el análisis no lineal de mínimos cuadrados y otras generalizaciones, utilizado en parámetros de ajuste 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 generales exactas más exitosas son:

Aproximación interior y exterior

En ambas estrategias, el conjunto sobre el cual se va a optimizar una función se aproxima mediante poliedros. En la aproximación interior, los poliedros están contenidos en el conjunto, mientras que en la aproximación exterior, los poliedros contienen el conjunto.

Métodos del 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 mediante desigualdades lineales, denominadas cortes. Estos procedimientos se utilizan popularmente para encontrar soluciones enteras a problemas de programación lineal entera mixta (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 enlace

Bifurcación y límite (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 limitación consiste en una enumeración sistemática de soluciones candidatas mediante 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 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 el momento por el algoritmo.

Métodos de intervalo

Aritmética de intervalos, matemáticas de intervalos, análisis de intervalos o 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 así desarrollar métodos numéricos que produzcan resultados confiables. La aritmética de intervalos ayuda a encontrar soluciones confiables y garantizadas a ecuaciones y problemas de optimización.

Métodos basados en geometría algebraica real

Álgebra real es la parte del álgebra relevante para la geometría algebraica real (y semialgebraica). 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 es lo que se llama un problema de optimización convencional. Es decir, se conocen con certeza todos los hechos (distancias entre cada punto de destino) necesarios para determinar el camino óptimo a seguir y el objetivo es analizar las posibles opciones de viaje para encontrar el que tenga la menor distancia total. Sin embargo, supongamos que en lugar de querer minimizar la distancia total recorrida para visitar cada destino deseado, queremos 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 inherentemente incierto (embotellamientos, 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 llevar 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únel estocástico

Túnel estocástico (STUN) es un enfoque de optimización global basado en el método de Monte Carlo: muestreo de la función que se minimizará objetivamente en el que la función se transforma de forma no lineal para permitir un túnel más fácil entre regiones. que contiene mínimos de función. La creació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.

Revenido paralelo

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 Markov. métodos de muestreo de la cadena Monte Carlo (MCMC) de manera más general. El método de intercambio de réplicas fue ideado originalmente por Swendsen, luego ampliado por Geyer y posteriormente desarrollado, 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.

Básicamente, se ejecutan N copias del sistema, inicializadas aleatoriamente, a diferentes temperaturas. Luego, basándose en el criterio de Metropolis, se intercambian configuraciones a diferentes temperaturas. La idea de este método. es poner a disposición de las simulaciones a bajas temperaturas configuraciones a altas temperaturas y viceversa. Esto da como resultado un conjunto muy robusto que es capaz de muestrear configuraciones de alta y baja energía. De esta manera, 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ísticas y metaheurísticas

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

• Optimización de la colonia de hormigas (ACO)
• Aniquilamiento simulado, una metaheurística probabilística genérica
• Tabu search, una extensión de búsqueda local capaz de escapar de la minima local
• 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 medida determinada de calidad
• algoritmos de optimización basados en el cisma (por ejemplo, optimización de partículas, optimización cognitiva social, optimización multiswarm y optimización de hormigas)
• algoritmos meméticos, combinando estrategias de búsqueda globales y locales
• Optimización de búsqueda reactiva (es decir, integración de técnicas de aprendizaje de máquinas sub-simbólicos en las heurísticas de búsqueda)
• Optimización graduada, una técnica que intenta resolver un problema de optimización difícil al resolver inicialmente un problema muy simplificado, y transformar progresivamente ese problema (a la vez que optimiza) hasta que sea equivalente al difícil problema de optimización.

Enfoques basados en metodologías de superficie de respuesta

• Optimización indirecta 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 usando estadísticas Bayesian