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

1. Formulação do Problema

O artigo aborda a otimização global determinística de uma função de média posterior treinada de Processo Gaussiano (GP), $\mu(x)$, sobre um domínio hiperretangular compacto.

• Contexto: Em fluxos de trabalho científicos e de engenharia, GPs são frequentemente treinados em dados de simulação ou experimentais caros para servir como substitutos. Uma vez treinados, esses modelos são incorporados em problemas de otimização (por exemplo, projeto, controle, calibração) onde o objetivo é minimizar a média posterior.
• Formulação Matemática: A média posterior é uma soma ponderada de $N$ termos de kernel centrados em pontos de treinamento:
  $$\mu(x) = \sum_{i=1}^N \alpha_i k_L(x, x_i)$$
  onde $\alpha_i$ são coeficientes derivados dos dados de treinamento (que podem ter sinais positivos e negativos mistos) e $k_L$ é um kernel estacionário (por exemplo, RBF, Matérn).
• Desafios:
  • Não convexidade: A função é uma soma ponderada não convexa e multimodal.
  • Escalabilidade: Solucionadores determinísticos exatos existentes (como BARON ou ANTIGONE) lutam conforme $N$ aumenta, pois devem relaxar cada termo de kernel simultaneamente, levando a limites fracos e crescimento exponencial na árvore de ramificação e limite.
  • Compromisso de Aproximação: Métodos baseados em aproximação melhoram a tratabilidade, mas resolvem um problema modificado, perdendo a garantia de otimalidade global para a média posterior exata.

2. Metodologia: PALM-Mean

Os autores propõem o PALM-Mean (Método de Limitação Inferencial Analítica por Partes), um algoritmo de ramificação e limite espacial em espaço reduzido projetado para preservar a exatidão enquanto melhora a escalabilidade.

Conceito Central: Limitação Inferencial Híbrida

O algoritmo explora a observação de que, em qualquer subdomínio específico (nó) do espaço de busca, apenas um subconjunto de pontos de treinamento (termos de kernel) influencia significativamente a forma local da média posterior. Termos correspondentes a pontos de treinamento distantes têm variação negligenciável sobre o nó.

O método particiona os termos de kernel em dois conjuntos com base em um limiar de importância heurístico $\rho$:

1. Termos Importantes ($I(h)$): Termos com grande potencial de influência no nó atual.
   • Tratamento: Estes são relaxados usando envoltórios lineares por partes (PWL) conscientes de sinal em uma variável de distância escalar (por exemplo, distância euclidiana escalada).
   • Mecanismo: Para kernels RBF, a variável de distância é a distância ao quadrado; para kernels Matérn, é a distância. O sinal do coeficiente $\alpha_i$ é tratado explicitamente:
     • Se $\alpha_i > 0$, o limite inferior usa a envoltória inferior PWL do kernel.
     • Se $\alpha_i < 0$, o limite inferior usa a envoltória superior PWL (pois multiplicar por um negativo inverte a desigualdade).
2. Termos Não Importantes ($U(h)$): Termos com pequeno potencial de influência.
   • Tratamento: Estes são limitados usando limites analíticos fechados e baratos.
   • Mecanismo: Como os kernels são monotonicamente decrescentes com a distância, os limites são derivados simplesmente calculando as distâncias escaladas mínima e máxima do ponto de treinamento ao hiperretângulo do nó.

Fluxo de Trabalho Algorítmico

1. Ramificação em Espaço Reduzido: A ramificação ocorre apenas sobre as variáveis de decisão originais $x$, não sobre variáveis auxiliares.
2. Limite Inferior do Nó: Em cada nó, o algoritmo constrói um Programa Quadraticamente Restrito com Inteiros Misto (MIQCP). O objetivo minimiza a soma das relaxações PWL para termos importantes e as constantes analíticas para termos não importantes.
3. Limite Superior do Nó: Obtido via otimização local (L-BFGS-B) da média posterior exata dentro do nó.
4. Convergência: O algoritmo garante convergência $\epsilon$-global porque a lacuna entre os limites por partes/analíticos e a função verdadeira desaparece conforme o diâmetro do nó se aproxima de zero.

3. Contribuições Principais

1. Estrutura de Limitação Inferencial Híbrida: Um procedimento novo que combina relaxações lineares por partes apertadas para termos críticos localmente com limites analíticos de baixo custo para o restante. Isso evita o gargalo computacional de relaxar todos os $N$ termos.
2. Relaxação Consciente de Sinal: Uma formulação matemática rigorosa que lida corretamente com os sinais mistos dos coeficientes do GP ($\alpha_i$) para garantir limites inferiores válidos, o que é crucial para somas não convexas.
3. Solucionador Exato Escalável: A introdução do PALM-Mean, que fornece uma solução global determinística para a média posterior exata, preenchendo a lacuna entre solucionadores exatos intratáveis e métodos de aproximação inexatos.
4. Garantias Teóricas: Prova da validade do limite inferior híbrido e da convergência $\epsilon$-global do algoritmo de ramificação e limite espacial.

4. Resultados Experimentais

Os autores avaliaram o PALM-Mean contra solucionadores de propósito geral de última geração (SCIP, MAiNGO, BARON) em benchmarks sintéticos e aplicações do mundo real.

• Benchmarks Sintéticos (Funções EggHolder e Schwefel):
  • Escalabilidade com $N$: À medida que o número de pontos de treinamento ($N$) aumentava (até 1.500), solucionadores de propósito geral falhavam em resolver instâncias dentro dos limites de tempo ou exigiam tempo excessivo. O PALM-Mean resolveu quase todas as instâncias, com a versão paralela de 16 núcleos mostrando acelerações significativas.
  • Escalabilidade com Dimensão: O PALM-Mean manteve desempenho superior conforme a dimensão de entrada aumentava, enquanto outros solucionadores degradavam rapidamente.
  • Tamanho da Árvore: O PALM-Mean explorou ordens de magnitude menos nós de ramificação e limite em comparação com SCIP e MAiNGO, indicando limites inferiores muito mais apertados e poda mais eficaz.
• Aplicações do Mundo Real:
  • Reação N-benzilação: O PALM-Mean resolveu o problema em ~15 segundos (16 núcleos), enquanto o SCIP levou ~107 segundos e MAiNGO/BARON atingiram limites de tempo com limites fracos.
  • Manufatura Aditiva Autônoma: Em uma instância mais difícil com 100 pontos de dados, apenas o PALM-Mean (16 núcleos) e o SCIP encontraram o ótimo global dentro do limite de 1 hora. O PALM-Mean foi mais rápido e utilizou uma árvore de busca drasticamente menor.

5. Significado e Impacto

• Preenchendo a Lacuna: O PALM-Mean resolve a lacuna metodológica específica onde métodos exatos existentes não escalam e métodos de aproximação sacrificam a correção. Ele permite otimização global certificada de substitutos GP treinados.
• Utilidade Prática: Isso é crítico para configurações científicas com poucos dados (comuns em química, ciência dos materiais e engenharia), onde GPs são o modelo substituto padrão e tomar decisões globais "seguras" (por exemplo, evitar condições operacionais inseguras) é primordial.
• Direções Futuras: Os autores observam que, embora o trabalho atual se concentre na média posterior, a perspectiva analítica por partes poderia ser estendida para otimizar a variância posterior do GP ou funções de aquisição (como Limite Inferior de Confiança), embora estes apresentem desafios computacionais adicionais devido a somas duplas.

Em resumo, o PALM-Mean representa um avanço significativo na otimização baseada em substitutos, aproveitando a estrutura específica de Processos Gaussianos para criar um algoritmo de otimização global escalável, exato e robusto.