Optimización global determinista

La optimización global determinista es una rama de la optimización matemática que se centra en encontrar las soluciones globales de un problema de optimización, proporcionando garantías teóricas de que la solución obtenida es, efectivamente, la global, dentro de una tolerancia predefinida. El término "optimización global determinista" se refiere generalmente a métodos de optimización completos o rigurosos (véase más adelante). Los métodos rigurosos convergen al óptimo global en un tiempo finito. Los métodos de optimización global determinista se utilizan normalmente cuando es imprescindible encontrar la solución global (es decir, cuando el único estado que se da de forma natural descrito por un modelo matemático es el mínimo global de un problema de optimización), cuando es extremadamente difícil encontrar una solución factible o, simplemente, cuando el usuario desea encontrar la mejor solución posible a un problema.

Neumaier ^{[ 1 ]} clasificó los métodos de optimización global en cuatro categorías, dependiendo del grado de rigor con el que se aproximan al óptimo, de la siguiente manera:

• Un método incompleto utiliza heurísticas intuitivas e ingeniosas para la búsqueda, pero carece de salvaguardas si la búsqueda se estanca en un mínimo local.
• Un método asintóticamente completo alcanza un mínimo global con certeza o, al menos, con probabilidad uno si se le permite ejecutarse indefinidamente, pero no tiene forma de saber cuándo se ha encontrado un minimizador global.
• Un método completo alcanza un mínimo global con certeza, suponiendo cálculos exactos y un tiempo de ejecución indefinidamente largo, y sabe, después de un tiempo finito, que se ha encontrado un minimizador global aproximado (dentro de las tolerancias prescritas).
• Un método riguroso alcanza un mínimo global con certeza y dentro de las tolerancias dadas, incluso en presencia de errores de redondeo, excepto en casos casi degenerados, donde las tolerancias pueden excederse.

Los métodos de optimización global deterministas suelen pertenecer a las dos últimas categorías. Cabe destacar que desarrollar un software riguroso es extremadamente difícil, ya que el proceso exige que todas las dependencias también estén codificadas con rigor.

Los métodos de optimización global deterministas requieren formas de acotar rigurosamente los valores de las funciones en regiones del espacio. Podría decirse que una diferencia principal entre los métodos deterministas y no deterministas en este contexto es que los primeros realizan cálculos en regiones del espacio de soluciones, mientras que los segundos los realizan en puntos individuales. Esto se logra explotando formas funcionales particulares (por ejemplo, relajaciones de McCormick ^{[ 2 ]} ) o utilizando análisis de intervalos para trabajar con formas funcionales más generales. En cualquier caso, se requiere acotar, razón por la cual los métodos de optimización global deterministas no pueden proporcionar un resultado riguroso al trabajar con código de caja negra , a menos que dicho código esté escrito explícitamente para devolver también cotas de función. Por esta razón, es común que los problemas de optimización global determinista se representen mediante un grafo computacional , ya que es sencillo sobrecargar todos los operadores de manera que los valores o derivadas de la función resultante produzcan resultados de intervalo (en lugar de escalares).

Los métodos de orden cero consisten en métodos que utilizan aritmética de intervalos de orden cero . ^{[ 3 ]} Un ejemplo representativo es la bisección de intervalos.

Los métodos de primer orden consisten en métodos que utilizan información de primer orden, por ejemplo, gradientes de intervalo o pendientes de intervalo.

Los métodos de segundo orden utilizan información de segundo orden, generalmente límites de valores propios derivados de matrices hessianas de intervalo . Una de las metodologías de segundo orden más generales para abordar problemas de tipo general es el algoritmo αBB .

• ANTIGONE : Algoritmos para la optimización global continua/entera de ecuaciones no lineales). ^{[ 4 ]} Es un software propietario, disponible a través de ANTIGONE, la plataforma de modelado GAMS . ^{[ 5 ]}
• BARON : BARON está disponible bajo los lenguajes de modelado AIMMS , AMPL y GAMS y en el servidor NEOS. ^{[ 6 ]} Es un software propietario. ^{[ 7 ]}
• Couenne : Convex Over and Under ENvelopes for Nonlinear Estimation (Couenne) es una biblioteca de código abierto ^{[ 8 ].}
• EAGO: Easy-Advanced Global Optimization (EAGO) ^{[ 9 ]} es un solucionador de código abierto en Julia (lenguaje de programación) . Fue desarrollado por la Universidad de Connecticut. ^{[ 10 ]}
• LINDO (Optimizador Lineal, Interactivo y Discreto) incluye capacidades de optimización global. ^{[ 11 ]}
• MAiNGO: Algoritmo basado en McCormick para optimización global no lineal de enteros mixtos (MAiNGO) ^{[ 12 ]} es un paquete de C++ con paralelización MPI y openMP y se proporciona como código abierto ^{[ 13 ]} bajo la Licencia Pública de Eclipse - v 2.0.
• Octeract Engine es un solucionador propietario con capacidades de paralelización. Es desarrollado y licenciado por Octeract ^{[ 14 ].}
• SCIP : SCIP es un conjunto de solucionadores de optimización de código abierto que, entre otros, resuelve programación no lineal de enteros mixtos (MINLP) ^{[ 15 ].}