An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functions

A continuación se presenta un resumen técnico detallado del artículo "Un algoritmo eficiente de ramificación y acotación espacial para la optimización global de funciones de media posterior de procesos gaussianos."

1. Planteamiento del Problema

El artículo aborda la optimización global determinista de una función de media posterior de un Proceso Gaussiano (GP) entrenado, $\mu(x)$, sobre un dominio hiperrectangular compacto.

• Contexto: En flujos de trabajo científicos e ingenieriles, los GPs se entrenan a menudo con datos de simulaciones costosas o experimentales para servir como sustitutos. Una vez entrenados, estos modelos se incrustan en problemas de optimización (por ejemplo, diseño, control, calibración) donde el objetivo es minimizar la media posterior.
• Formulación Matemática: La media posterior es una suma ponderada de $N$ términos de núcleo centrados en puntos de entrenamiento:
  $$\mu(x) = \sum_{i=1}^N \alpha_i k_L(x, x_i)$$
  donde $\alpha_i$ son coeficientes derivados de los datos de entrenamiento (que pueden tener signos positivos y negativos mixtos) y $k_L$ es un núcleo estacionario (por ejemplo, RBF, Matérn).
• Desafíos:
  • No convexidad: La función es una suma ponderada no convexa y multimodal.
  • Escalabilidad: Los solucionadores deterministas exactos existentes (como BARON o ANTIGONE) tienen dificultades a medida que aumenta $N$, ya que deben relajar simultáneamente cada término del núcleo, lo que conduce a cotas débiles y a un crecimiento exponencial en el árbol de ramificación y acotación.
  • Compensación de aproximación: Los métodos basados en aproximación mejoran la tratabilidad pero resuelven un problema modificado, perdiendo la garantía de optimalidad global para la media posterior exacta.

2. Metodología: PALM-Mean

Los autores proponen PALM-Mean (Método de Acotación Inferior Analítica por Partes), un algoritmo de ramificación y acotación espacial en espacio reducido diseñado para preservar la exactitud mientras mejora la escalabilidad.

Concepto Central: Acotación Inferior Híbrida

El algoritmo explota la observación de que, en cualquier subdominio específico (nodo) del espacio de búsqueda, solo un subconjunto de puntos de entrenamiento (términos de núcleo) influye significativamente en la forma local de la media posterior. Los términos correspondientes a puntos de entrenamiento distantes tienen una variación negligible sobre el nodo.

El método divide los términos de núcleo en dos conjuntos basándose en un umbral heurístico de importancia $\rho$:

1. Términos Importantes ($I(h)$): Términos con gran influencia potencial en el nodo actual.
   • Tratamiento: Estos se relajan utilizando envolturas lineales por partes (PWL) conscientes del signo en una variable de distancia escalar (por ejemplo, distancia euclidiana escalada).
   • Mecanismo: Para núcleos RBF, la variable de distancia es la distancia al cuadrado; para núcleos Matérn, es la distancia. El signo del coeficiente $\alpha_i$ se maneja explícitamente:
     • Si $\alpha_i > 0$, la cota inferior utiliza la envoltura inferior PWL del núcleo.
     • Si $\alpha_i < 0$, la cota inferior utiliza la envoltura superior PWL (ya que multiplicar por un negativo invierte la desigualdad).
2. Términos No Importantes ($U(h)$): Términos con poca influencia potencial.
   • Tratamiento: Estos se acotan utilizando cotas analíticas cerradas y económicas.
   • Mecanismo: Dado que los núcleos son monótonamente decrecientes con la distancia, las cotas se derivan simplemente calculando las distancias escaladas mínima y máxima desde el punto de entrenamiento hasta el hiperrectángulo del nodo.

Flujo de Trabajo Algorítmico

1. Ramificación en Espacio Reducido: La ramificación ocurre solo sobre las variables de decisión originales $x$, no sobre variables auxiliares.
2. Cota Inferior del Nodo: En cada nodo, el algoritmo construye un Programa Cuadrático con Restricciones Mixtas Enteras (MIQCP). La función objetivo minimiza la suma de las relajaciones PWL para los términos importantes y las constantes analíticas para los términos no importantes.
3. Cota Superior del Nodo: Se obtiene mediante optimización local (L-BFGS-B) de la media posterior exacta dentro del nodo.
4. Convergencia: El algoritmo garantiza la convergencia global $\epsilon$ porque la brecha entre las cotas lineales por partes/analíticas y la función verdadera desaparece a medida que el diámetro del nodo tiende a cero.

3. Contribuciones Clave

1. Marco de Acotación Inferior Híbrido: Un procedimiento novedoso que combina relajaciones lineales por partes ajustadas para términos críticos localmente con cotas analíticas de bajo costo para el resto. Esto evita el cuello de botella computacional de relajar todos los $N$ términos.
2. Relajación Consciente del Signo: Una formulación matemática rigurosa que maneja correctamente los signos mixtos de los coeficientes del GP ($\alpha_i$) para garantizar cotas inferiores válidas, lo cual es crucial para sumas no convexas.
3. Solucionador Exacto Escalable: La introducción de PALM-Mean, que proporciona una solución global determinista para la media posterior exacta, cerrando la brecha entre solucionadores exactos intratables y métodos de aproximación inexactos.
4. Garantías Teóricas: Demostración de la validez de la cota inferior híbrida y de la convergencia global $\epsilon$ del algoritmo de ramificación y acotación espacial.

4. Resultados Experimentales

Los autores evaluaron PALM-Mean frente a solucionadores de propósito general de vanguardia (SCIP, MAiNGO, BARON) en benchmarks sintéticos y aplicaciones del mundo real.

• Benchmarks Sintéticos (Funciones EggHolder y Schwefel):
  • Escalado con $N$: A medida que aumentaba el número de puntos de entrenamiento ($N$) (hasta 1.500), los solucionadores de propósito general no lograron resolver instancias dentro de los límites de tiempo o requirieron un tiempo excesivo. PALM-Mean resolvió casi todas las instancias, mostrando aceleraciones significativas con la versión paralela de 16 núcleos.
  • Escalado con Dimensionalidad: PALM-Mean mantuvo un rendimiento superior a medida que aumentaba la dimensión de entrada, mientras que otros solucionadores se degradaron rápidamente.
  • Tamaño del Árbol: PALM-Mean exploró órdenes de magnitud menos nodos de ramificación y acotación en comparación con SCIP y MAiNGO, lo que indica cotas inferiores mucho más ajustadas y una poda más efectiva.
• Aplicaciones del Mundo Real:
  • Reacción de N-benzilación: PALM-Mean resolvió el problema en ~15 segundos (16 núcleos), mientras que SCIP tardó ~107 segundos y MAiNGO/BARON alcanzaron los límites de tiempo con cotas débiles.
  • Fabricación Aditiva Autónoma: En una instancia más difícil con 100 puntos de datos, solo PALM-Mean (16 núcleos) y SCIP encontraron el óptimo global dentro del límite de 1 hora. PALM-Mean fue más rápido y utilizó un árbol de búsqueda drásticamente más pequeño.

5. Significado e Impacto

• Cerrando la Brecha: PALM-Mean resuelve la brecha metodológica específica donde los métodos exactos existentes no escalan y los métodos de aproximación sacrifican la corrección. Permite la optimización global certificada de sustitutos GP entrenados.
• Utilidad Práctica: Esto es crítico en entornos científicos con pocos datos (comunes en química, ciencia de materiales e ingeniería) donde los GPs son el modelo sustituto estándar, y tomar decisiones globales "seguras" (por ejemplo, evitar condiciones de operación inseguras) es primordial.
• Futuras Direcciones: Los autores señalan que, aunque el trabajo actual se centra en la media posterior, la perspectiva analítica por partes podría extenderse a la optimización de la varianza posterior del GP o funciones de adquisición (como el Límite Inferior de Confianza), aunque estos presentan desafíos computacionales adicionales debido a las dobles sumas.

En resumen, PALM-Mean representa un avance significativo en la optimización basada en sustitutos al aprovechar la estructura específica de los Procesos Gaussianos para crear un algoritmo de optimización global escalable, exacto y robusto.