Optimización global

Rama de las matemáticas

La optimización global es una rama de las matemáticas aplicadas y del análisis numérico que intenta encontrar los mínimos o máximos globales de una función o de un conjunto de funciones en un conjunto dado. Se suele describir 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 \subset \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 buscar 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 con frecuencia no son aplicables y el uso de estrategias de solución numérica a menudo conduce a desafíos muy difíciles.

Aplicaciones

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

• Predicción de la estructura de proteínas (minimizar 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 viajante y diseño de circuitos eléctricos (minimizar la longitud del camino)
• 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 del peor de los casos
• Problemas matemáticos (por ejemplo, la conjetura de Kepler )
• Problemas de empaquetamiento 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.
• Vasos giratorios
• Calibración de modelos de propagación de radio y de muchos otros modelos en las ciencias y la ingeniería.
• Ajuste de curvas, como el análisis de mínimos cuadrados no lineales y otras generalizaciones, se utilizan para ajustar los parámetros del modelo a datos experimentales en química, física, biología, economía, finanzas, medicina, astronomía e ingeniería.
• Planificación de la radioterapia IMRT

Métodos deterministas

Las estrategias generales exactas más exitosas son:

Aproximación interna y externa

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

Métodos de corte por plano

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 . Dichos procedimientos se utilizan popularmente para encontrar soluciones enteras a problemas de programación lineal entera mixta (MILP), así como para resolver problemas de optimización convexa generales, no necesariamente diferenciables . El uso de planos de corte para resolver MILP fue introducido por Ralph E. Gomory y Václav Chvátal .

Métodos de ramificación y acotación

El algoritmo de ramificación y acotación ( BB o B&B ) es un paradigma de diseño de algoritmos para problemas de optimización discreta y combinatoria . Un algoritmo de ramificación y acotación consiste en una enumeración sistemática de soluciones candidatas mediante una búsqueda en el espacio de estados : se piensa que el conjunto de soluciones candidatas forma un árbol con raíz 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 verifica con los límites superior e inferior estimados en la solución óptima, y ​​se descarta si no puede producir una mejor solución que la mejor encontrada hasta el momento por el algoritmo.

Métodos de intervalo

La aritmética de intervalos , matemática de intervalos , análisis de intervalos o cálculo de intervalos es un método desarrollado por matemáticos desde los años 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, de este modo, desarrollar métodos numéricos que arrojen 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

El álgebra real es la parte del álgebra que es relevante para la geometría algebraica real (y semialgebraica). Se ocupa principalmente del estudio de cuerpos ordenados y anillos ordenados (en particular cuerpos reales cerrados ) 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 Montecarlo, 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 repasar las posibles opciones de viaje para llegar a la que tenga la menor distancia total. Sin embargo, supongamos que en lugar de querer minimizar la distancia total recorrida para visitar cada destino deseado, quisiéramos 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 (atascos de tráfico, hora del día, etc.). Como resultado, para determinar nuestra ruta óptima querríamos utilizar la simulación - optimización para comprender primero el rango de tiempos potenciales que podría tomar 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 la mejor ruta a seguir teniendo en cuenta esa incertidumbre.

Túnel estocástico

El efecto 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 va a minimizar objetivamente, en el que la función se transforma de manera no lineal para permitir un efecto túnel más fácil entre las regiones que contienen los mínimos de la función. Un efecto túnel más fácil 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 por intercambio de réplicas , es un método de simulación destinado a mejorar las propiedades dinámicas de las simulaciones del método Monte Carlo de sistemas físicos y, de manera más general, de los métodos de muestreo Monte Carlo de cadena de Markov (MCMC). El método de intercambio de réplicas fue ideado originalmente por Swendsen, ^[1] luego ampliado por Geyer ^[2] y desarrollado más tarde, entre otros, por Giorgio Parisi ., ^{[3] [4]} Sugita y Okamoto formularon una versión de dinámica molecular del templado paralelo: ^[5] 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, según el criterio de Metropolis, se intercambian las 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 energía alta y baja. 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, incluyendo:

• 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 intentando iterativamente mejorar una solución candidata con respecto a una medida de calidad dada.
• Algoritmos de optimización basados ​​en enjambres (por ejemplo, optimización de enjambres de partículas , optimización cognitiva social , optimización de múltiples enjambres 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 subsimbólico 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. ^{[6] [7] [8]}

Enfoques basados ​​en la metodología de superficies 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 ^[9]

Véase también

• Optimización global determinista
• Optimización del diseño multidisciplinario
• Optimización multiobjetivo
• Optimización (matemáticas)

Notas al pie

1. Swendsen RH y Wang JS (1986) Réplica de simulación de Monte Carlo de vidrios de espín Physical Review Letters 57: 2607–2609
2. CJ Geyer, (1991) en Computing Science and Statistics , Actas del 23º Simposio sobre la Interfaz, American Statistical Association, Nueva York, pág. 156.
3. Marco Falcioni y Michael W. Deem (1999). "Un esquema de Monte Carlo sesgado para la solución de la estructura de la zeolita". J. Chem. Phys . 110 (3): 1754–1766. arXiv : cond-mat/9809085 . Código Bibliográfico : 1999JChPh.110.1754F. doi : 10.1063/1.477812. S2CID  : 13963102.
4. David J. Earl y Michael W. Deem (2005) "Templado paralelo: teoría, aplicaciones y nuevas perspectivas", Phys. Chem. Chem. Phys. , 7, 3910
5. Y. Sugita y Y. Okamoto (1999). "Método de dinámica molecular de intercambio de réplicas para el plegamiento de proteínas". Chemical Physics Letters . 314 (1–2): 141–151. Bibcode :1999CPL...314..141S. doi :10.1016/S0009-2614(99)01123-9.
6. Thacker, Neil; Cootes, Tim (1996). "Métodos de optimización de resolución múltiple y no convexidad graduada". Visión a través de la optimización .
7. Blake, Andrew; Zisserman, Andrew (1987). Reconstrucción visual. MIT Press. ISBN 0-262-02271-0.^{[ página necesaria ]}
8. Hossein Mobahi, John W. Fisher III. Sobre el vínculo entre la continuación de la homotopía gaussiana y las envolventes convexas, en Lecture Notes in Computer Science (EMMCVPR 2015), Springer, 2015.
9. Jonas Mockus (2013). Enfoque bayesiano para la optimización global: teoría y aplicaciones. Kluwer Academic.

Referencias

Optimización global determinista:

• R. Horst, H. Tuy, Optimización global: enfoques deterministas, Springer, 1996.
• R. Horst, PM Pardalos y NV Thoai, Introducción a la optimización global, segunda edición. Kluwer Academic Publishers, 2000.
• A. Neumaier, Búsqueda completa en optimización global continua y satisfacción de restricciones, págs. 271–369 en: Acta Numerica 2004 (A. Iserles, ed.), Cambridge University Press 2004.
• M. Mongeau, H. Karsenty, V. Rouzé y J.-B. Hiriart-Urruty, Comparación de software de dominio público para optimización global de caja negra. Optimization Methods & Software 13(3), págs. 203–226, 2000.
• JD Pintér, Optimización global en acción: optimización continua y de Lipschitz: algoritmos, implementaciones y aplicaciones. Kluwer Academic Publishers, Dordrecht, 1996. Actualmente distribuido por Springer Science and Business Media, Nueva York. Este libro también analiza los métodos de optimización global estocástica.
• L. Jaulin, M. Kieffer, O. Didrit, E. Walter (2001). Análisis de intervalos aplicado. Berlín: Springer.
• ER Hansen (1992), Optimización global mediante análisis de intervalos, Marcel Dekker, Nueva York.

Para recocido simulado:

• Kirkpatrick, S.; Gelatt, CD; Vecchi, MP (1983-05-13). "Optimización mediante recocido simulado". Science . 220 (4598). Asociación Estadounidense para el Avance de la Ciencia (AAAS): 671–680. Bibcode :1983Sci...220..671K. doi :10.1126/science.220.4598.671. ISSN  0036-8075. PMID  17813860. S2CID  205939.

Para optimizar la búsqueda reactiva:

• Roberto Battiti , M. Brunato y F. Mascia, Búsqueda reactiva y optimización inteligente, Operations Research/Computer Science Interfaces Series, vol. 45, Springer, noviembre de 2008. ISBN 978-0-387-09623-0 

Para métodos estocásticos:

• A. Zhigljavsky . Teoría de la búsqueda aleatoria global. Matemáticas y sus aplicaciones. Kluwer Academic Publishers. 1991.
• Hamacher, K (2006). "Adaptación en optimización global por efecto túnel estocástico de paisajes energéticos potenciales complejos". Europhysics Letters (EPL) . 74 (6). IOP Publishing: 944–950. Bibcode :2006EL.....74..944H. doi :10.1209/epl/i2006-10058-0. ISSN  0295-5075. S2CID  250761754.
• Hamacher, K.; Wenzel, W. (1999-01-01). "Comportamiento de escalado de algoritmos de minimización estocástica en un paisaje de embudo perfecto". Physical Review E . 59 (1): 938–941. arXiv : physics/9810035 . Bibcode :1999PhRvE..59..938H. doi :10.1103/physreve.59.938. ISSN  1063-651X. S2CID  119096368.
• Wenzel, W.; Hamacher, K. (12 de abril de 1999). "Enfoque de efecto túnel estocástico para la minimización global de paisajes complejos de energía potencial". Physical Review Letters . 82 (15). American Physical Society (APS): 3003–3007. arXiv : physics/9903008 . Bibcode :1999PhRvL..82.3003W. doi :10.1103/physrevlett.82.3003. ISSN  0031-9007. S2CID  5113626.

Para templado paralelo:

• Hansmann, Ulrich HE (1997). "Algoritmo de templado paralelo para estudios conformacionales de moléculas biológicas". Chemical Physics Letters . 281 (1–3). Elsevier BV: 140–150. arXiv : physics/9710041 . Bibcode :1997CPL...281..140H. doi :10.1016/s0009-2614(97)01198-6. ISSN  0009-2614. S2CID  14137470.

Para métodos de continuación:

• Zhijun Wu. El esquema de transformación de energía efectiva como un enfoque de continuación especial para la optimización global con aplicación a la conformación molecular. Informe técnico, Argonne National Lab., IL (Estados Unidos), noviembre de 1996.

Para consideraciones generales sobre la dimensionalidad del dominio de definición de la función objetivo:

• Hamacher, Kay (2005). "Sobre la optimización global estocástica de funciones unidimensionales". Physica A: Mecánica estadística y sus aplicaciones . 354 . Elsevier BV: 547–557. Bibcode :2005PhyA..354..547H. doi :10.1016/j.physa.2005.02.028. ISSN  0378-4371.

Para estrategias que permitan comparar métodos de optimización global deterministas y estocásticos

Enlaces externos

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