Luus–Jaakola

En ingeniería computacional , Luus–Jaakola (LJ) denota una heurística para la optimización global de una función de valor real. ^[1] En el uso de ingeniería, LJ no es un algoritmo que termina con una solución óptima; ni es un método iterativo que genera una secuencia de puntos que converge a una solución óptima (cuando existe una). Sin embargo, cuando se aplica a una función dos veces continuamente diferenciable, la heurística LJ es un método iterativo adecuado, que genera una secuencia que tiene una subsecuencia convergente; para esta clase de problemas, se recomienda el método de Newton y disfruta de una tasa cuadrática de convergencia, mientras que no se ha dado ningún análisis de tasa de convergencia para la heurística LJ. ^[1] En la práctica, la heurística LJ se ha recomendado para funciones que no necesitan ser ni convexas ni diferenciables ni localmente Lipschitz : La heurística LJ no utiliza un gradiente o subgradiente cuando uno está disponible, lo que permite su aplicación a problemas no diferenciables y no convexos.

Propuesto por Luus y Jaakola, ^[2] LJ genera una secuencia de iteraciones. La siguiente iteración se selecciona de una muestra de un vecindario de la posición actual utilizando una distribución uniforme . Con cada iteración, el vecindario disminuye, lo que obliga a una subsecuencia de iteraciones a converger a un punto de agrupamiento. ^[1]

Luus ha aplicado LJ en control óptimo , ^{[3] [4]} diseño de transformadores , ^[5] procesos metalúrgicos , ^[6] e ingeniería química . ^[7]

En cada paso, la heurística LJ mantiene una caja de la que toma muestras de puntos de forma aleatoria, utilizando una distribución uniforme en la caja. Para una función unimodal , la probabilidad de reducir la función objetivo disminuye a medida que la caja se acerca a un mínimo. La imagen muestra un ejemplo unidimensional.

Sea la función de aptitud o de costo que debe minimizarse. Designemos una posición o solución candidata en el espacio de búsqueda. La heurística LJ itera los siguientes pasos: ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} }$${\displaystyle {\textbf {x}}\in \mathbb {R} ^{n}}$

• Inicialice x  ~  U ( b _lo , b _up ) con una posición uniforme aleatoria en el espacio de búsqueda, donde b _lo y b _up son los límites inferior y superior, respectivamente.
• Establezca el rango de muestreo inicial para cubrir todo el espacio de búsqueda (o una parte de él): d  =  b _up  −  b _lo
• Hasta que se cumpla un criterio de terminación (por ejemplo, número de iteraciones realizadas o se alcance la aptitud adecuada), repita lo siguiente:
  • Elija un vector aleatorio a  ~  U (− d ,  d )
  • Agregue esto a la posición actual x para crear la nueva posición potencial y  =  x  +  a
  • Si ( f ( y ) <  f ( x )) entonces muévase a la nueva posición estableciendo x  =  y , de lo contrario disminuya el rango de muestreo: d  =  0,95  d
• Ahora x ocupa la mejor posición encontrada.

Luus señala que los algoritmos ARS (búsqueda aleatoria adaptativa) propuestos hasta la fecha difieren en muchos aspectos. ^[8]

• Procedimiento de generación de puntos de ensayo aleatorios.
• Número de bucles internos (NIL, el número de puntos de búsqueda aleatorios en cada ciclo).
• Número de ciclos (NEL, número de bucles externos).
• Coeficiente de contracción del tamaño de la región de búsqueda. (Algunos valores de ejemplo son 0,95 a 0,60).
  • Si la tasa de reducción de la región es la misma para todas las variables o una tasa diferente para cada variable (llamado algoritmo M-LJ).
  • Si la tasa de reducción de la región es constante o sigue otra distribución (por ejemplo, gaussiana).
• Si incorporar una búsqueda de línea.
• Si se deben considerar las restricciones de los puntos aleatorios como criterios de aceptación o si se debe incorporar una penalización cuadrática.

Nair demostró un análisis de convergencia. Para funciones dos veces continuamente diferenciables, la heurística LJ genera una secuencia de iteraciones que tienen una subsecuencia convergente. ^[1] Para esta clase de problemas, el método de Newton es el método de optimización habitual y tiene convergencia cuadrática ( independientemente de la dimensión del espacio, que puede ser un espacio de Banach , según el análisis de Kantorovich ).

Sin embargo, según el análisis de Yudin y Nemirovsky, la complejidad de minimización en el peor de los casos en la clase de funciones unimodales crece exponencialmente en la dimensión del problema. El análisis de Yudin-Nemirovsky implica que ningún método puede ser rápido en problemas de alta dimensión que carecen de convexidad:

"El crecimiento catastrófico [en el número de iteraciones necesarias para alcanzar una solución aproximada con una precisión dada] a medida que [el número de dimensiones aumenta hasta el infinito] muestra que no tiene sentido plantear la cuestión de construir métodos universales para resolver... problemas de cualquier dimensionalidad apreciable 'en general'. Es interesante observar que la misma [conclusión] es válida para... problemas generados por funciones uni-extremales [es decir, unimodales] (pero no convexas)". ^[9]

Cuando se aplica a problemas dos veces continuamente diferenciables, la tasa de convergencia de la heurística LJ disminuye a medida que aumenta el número de dimensiones. ^[10]

• La optimización aleatoria es una familia relacionada de métodos de optimización que toman muestras de distribuciones generales, por ejemplo, la distribución uniforme.
• La búsqueda aleatoria es una familia relacionada de métodos de optimización que toman muestras de distribuciones generales, por ejemplo, una distribución uniforme en la esfera unitaria .
• La búsqueda de patrones se utiliza en observaciones ruidosas, especialmente en la metodología de superficies de respuesta en ingeniería química . No requiere que los usuarios programen gradientes o hessianos.