Optimización global

La optimización global es una rama de la investigación operativa , las matemáticas aplicadas y el análisis numérico que intenta encontrar el mínimo o máximo global de una función o un conjunto de funciones en un conjunto dado. Generalmente se describe como un problema de minimización porque la maximización de la función de valor real $g(x)$ es equivalente a la minimización de la función $f(x):=(-1)\cdot g(x)$ .

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

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

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

La optimización global se distingue de la optimización local por centrarse en encontrar el mínimo o el máximo en un conjunto dado, en lugar de encontrar mínimos o máximos locales . Encontrar un mínimo local arbitrario es relativamente sencillo mediante 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 a menudo no son aplicables y el uso de estrategias de solución numérica suele plantear desafíos muy complejos.

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 recorrido)
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 escenario
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ámica molecular consiste en una optimización inicial de la energía del sistema que se va a simular.
Vasos giratorios
Calibración de modelos de propagación radioeléctrica y de muchos otros modelos en las ciencias y la ingeniería.
El ajuste de curvas, como el análisis de mínimos cuadrados no lineales y otras generalizaciones, se utiliza para ajustar parámetros de modelos 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 exactas generales más exitosas son:

Aproximación interna y externa

En ambas estrategias, el conjunto sobre el cual se optimiza 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 el conjunto.

Métodos de planos de corte

El método de planos de corte es un término general que engloba 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 comúnmente para encontrar soluciones enteras a problemas de programación lineal entera mixta (PLIM), así como para resolver problemas de optimización convexa generales, no necesariamente diferenciables . El uso de planos de corte para resolver PLIM 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 . Consiste en una enumeración sistemática de soluciones candidatas mediante la búsqueda en el espacio de estados : el conjunto de soluciones candidatas se concibe como un árbol con raíz , donde se encuentra el conjunto completo. El algoritmo explora las ramas de este árbol, que representan subconjuntos del conjunto de soluciones. Antes de enumerar las soluciones candidatas de una rama, esta se compara con los límites superiores e inferiores estimados para la solución óptima y se descarta si no puede generar una solución mejor que la mejor encontrada hasta el momento por el algoritmo.

Métodos de intervalo

La aritmética de intervalos , las matemáticas 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 para limitar los errores de redondeo y de medición en los cálculos matemáticos y, de este modo, desarrollar métodos numéricos que produzcan resultados fiables. La aritmética de intervalos ayuda a encontrar soluciones fiables y garantizadas para ecuaciones y problemas de optimización.

Métodos basados en la geometría algebraica real

El álgebra real es la rama del álgebra relevante para la geometría algebraica (y semialgebraica) real. Se centra principalmente en el 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 . Puede utilizarse en optimización convexa .

Métodos estocásticos

Existen varios algoritmos basados en el método de 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 es lo que se denomina un problema de optimización convencional. Es decir, se conocen con certeza todos los datos (distancias entre cada punto de destino) necesarios para determinar la ruta óptima, y el objetivo es analizar las posibles opciones de viaje para encontrar la que presente la menor distancia total. Sin embargo, supongamos que, en lugar de minimizar la distancia total recorrida para visitar cada destino, queremos minimizar el tiempo total necesario para llegar a cada uno. Esto va más allá de la optimización convencional, ya que el tiempo de viaje es inherentemente incierto (atascos, hora del día, etc.). Por lo tanto, para determinar nuestra ruta óptima, necesitarí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 en este caso por una distribución de probabilidad 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.

Tunelización estocástica

El método de tunelización estocástica (STUN) es una técnica de optimización global basada en el método de Monte Carlo . Consiste en el muestreo de la función que se pretende minimizar objetivamente, donde la función se transforma de forma no lineal para facilitar la tunelización entre las regiones que contienen mínimos de la función. Esta tunelización 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 del método de Monte Carlo de sistemas físicos, y de los métodos de muestreo de Monte Carlo de cadena de Markov (MCMC) en general. El método de intercambio de réplicas fue ideado originalmente por Swendsen, ^{[ 1 ]} luego extendido por Geyer ^{[ 2 ]} y posteriormente desarrollado, entre otros, por Giorgio Parisi ., ^{[ 3 ]}^{[ 4 ]} Sugita y Okamoto formularon una versión de dinámica molecular del templado paralelo: ^{[ 5 ]} esta se conoce habitualmente 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 configuraciones a distintas temperaturas. La idea de este método es 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 capaz de muestrear configuraciones tanto de baja como de alta energía. De esta manera, se pueden calcular con gran precisión propiedades termodinámicas como el calor específico, que generalmente no se calcula bien en el conjunto canónico.

Heurísticas y metaheurísticas

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

Optimización por colonia de hormigas (ACO)
Recocido simulado , una metaheurística probabilística genérica
La búsqueda tabú , una extensión de la búsqueda local capaz de escapar de 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 por enjambre de partículas , optimización cognitiva social , optimización multi-enjambre y optimización por colonia 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ólicas en heurísticas de búsqueda)
Optimización gradual , una técnica que intenta resolver un problema de optimización difícil resolviendo inicialmente un problema muy simplificado y transformándolo progresivamente (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ística bayesiana ^{[ 9 ].}

Véase también

Notas a pie de página

↑ Swendsen RH y Wang JS (1986) Simulación de réplica de Monte Carlo de vidrios de espín Physical Review Letters 57 : 2607–2609
↑ CJ Geyer, (1991) en Computing Science and Statistics , Actas del 23.er Simposio sobre la Interfaz, American Statistical Association, Nueva York, pág. 156.
↑ 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 . Bibcode : 1999JChPh.110.1754F . doi : 10.1063/1.477812 . S2CID 13963102 .
↑ David J. Earl y Michael W. Deem (2005) "Templado paralelo: teoría, aplicaciones y nuevas perspectivas" , Phys. Chem. Chem. Phys. , 7, 3910
↑ 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 .
↑ Thacker, Neil; Cootes, Tim (1996). "Métodos de optimización de no convexidad graduada y multirresolución" . Vision Through Optimization .
↑ Blake, Andrew; Zisserman, Andrew (1987). Reconstrucción visual . MIT Press. ISBN 0-262-02271-0.
↑ Hossein Mobahi, John W. Fisher III. Sobre el vínculo entre la continuación homotópica gaussiana y las envolventes convexas , en Lecture Notes in Computer Science (EMMCVPR 2015), Springer, 2015.
↑ 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, P.M. Pardalos y N.V. 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), pp. 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 aborda 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 el 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 la optimización de 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 la optimización global de tunelización estocástica de paisajes de energía potencial complejos". Europhysics Letters . 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 escalamiento 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. (1999-04-12). "Enfoque de tunelización estocástica para la minimización global de paisajes de energía potencial complejos". 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 el 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. Esquema de transformación de energía eficaz como enfoque de continuación especial para la optimización global con aplicación a la conformación molecular . Informe técnico, Laboratorio Nacional Argonne, Illinois (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.

[1] Swendsen RH y Wang JS (1986) Simulación de réplica 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.er 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 . Bibcode : 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 no convexidad graduada y multirresolución" . Vision Through Optimization .

[7] Blake, Andrew; Zisserman, Andrew (1987). Reconstrucción visual . MIT Press. ISBN 0-262-02271-0.

[mobahi2015-8] Hossein Mobahi, John W. Fisher III. Sobre el vínculo entre la continuación homotópica 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.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ].