Para la optimización matemática , la búsqueda de coordenadas multinivel ( MCS ) es un algoritmo eficiente [1] para la optimización global con restricciones de límites que utiliza solo valores de funciones . [2]
Para ello, el espacio de búsqueda n-dimensional se representa mediante un conjunto de hipercubos (cajas) que no se intersecan. A continuación, las cajas se dividen iterativamente a lo largo de un plano de eje según el valor de la función en un punto representativo de la caja (y sus vecinas) y el tamaño de la caja. Estos dos criterios de división se combinan para formar una búsqueda global mediante la división de cajas grandes y una búsqueda local mediante la división de áreas para las que el valor de la función es adecuado.
Además, se puede utilizar una búsqueda local que combine un interpolador cuadrático (multidimensional) de la función y búsquedas lineales para aumentar el rendimiento del algoritmo ( MCS con búsqueda local ); en este caso, se utiliza el MCS simple para proporcionar los puntos de partida (iniciales). La información proporcionada por las búsquedas locales (mínimos locales de la función objetivo) se devuelve al optimizador y afecta a los criterios de división, lo que da como resultado una agrupación de muestras reducida alrededor de los mínimos locales, una convergencia más rápida y una mayor precisión.
El flujo de trabajo de MCS se visualiza en las figuras 1 y 2. Cada paso del algoritmo se puede dividir en cuatro etapas:
En cada paso, el punto verde con el halo amarillo temporal es el único punto base de la caja; cada caja tiene asociado un valor del objetivo, es decir, su valor en el punto base de la caja.
Para determinar si una caja se dividirá, se utilizan dos criterios de división separados. El primero, la división por rango , garantiza que las cajas grandes que no se han dividido con demasiada frecuencia se dividirán eventualmente. Si se aplica, entonces el punto de división se determina fácilmente en una fracción fija de la longitud del lado que se está dividiendo. El segundo, la división por ganancia esperada , emplea un modelo cuadrático parabólico unidimensional local (sustituto) a lo largo de una sola coordenada. En este caso, el punto de división se define como el mínimo del sustituto a lo largo de un segmento de línea y la caja se divide solo si el valor del interpolador (que sirve como proxy del valor verdadero del objetivo) es menor que el mejor valor de la función muestreada actual.
Se garantiza que el algoritmo convergerá al mínimo global en el largo plazo (es decir, cuando el número de evaluaciones de la función y la profundidad de búsqueda sean arbitrariamente grandes) si la función objetivo es continua en la vecindad del minimizador global. Esto se desprende del hecho de que cualquier caja se volverá arbitrariamente pequeña con el tiempo, por lo que el espaciamiento entre muestras tiende a cero a medida que el número de evaluaciones de la función tiende a infinito.
El MCS está diseñado para implementarse de manera recursiva y eficiente con la ayuda de árboles . Con este enfoque, la cantidad de memoria requerida es independiente de la dimensionalidad del problema, ya que los puntos de muestreo no se almacenan explícitamente. En cambio, solo se guarda una única coordenada de cada muestra y las coordenadas restantes se pueden recuperar rastreando el historial de una caja hasta la raíz (caja inicial). Este método fue sugerido por los autores y utilizado en su implementación original. [2]
