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

1. Enunciato del Problema

Il documento affronta l'ottimizzazione globale deterministica di una funzione di media a posteriori addestrata di un Processo Gaussiano (GP), $\mu(x)$, su un dominio iperrettangolare compatto.

• Contesto: Nei flussi di lavoro scientifici e ingegneristici, i GP sono spesso addestrati su dati di simulazione o sperimentali costosi per fungere da surrogati. Una volta addestrati, questi modelli sono incorporati in problemi di ottimizzazione (ad esempio, progettazione, controllo, calibrazione) dove l'obiettivo è minimizzare la media a posteriori.
• Formulazione Matematica: La media a posteriori è una somma pesata di $N$ termini di kernel centrati sui punti di addestramento:
  $$\mu(x) = \sum_{i=1}^N \alpha_i k_L(x, x_i)$$
  dove $\alpha_i$ sono coefficienti derivati dai dati di addestramento (che possono avere segni positivi e negativi misti) e $k_L$ è un kernel stazionario (ad esempio, RBF, Matérn).
• Sfide:
  • Non convessità: La funzione è una somma pesata non convessa e multimodale.
  • Scalabilità: I solutori deterministici esatti esistenti (come BARON o ANTIGONE) faticano all'aumentare di $N$ perché devono rilassare simultaneamente ogni termine di kernel, portando a limiti deboli e a una crescita esponenziale nell'albero branch-and-bound.
  • Compromesso di approssimazione: I metodi basati sull'approssimazione migliorano la trattabilità ma risolvono un problema modificato, perdendo la garanzia di ottimalità globale per la media a posteriori esatta.

2. Metodologia: PALM-Mean

Gli autori propongono PALM-Mean (Metodo di Limitazione Inferiore Piecewise-Analitico), un algoritmo di branch-and-bound spaziale a spazio ridotto progettato per preservare l'esattezza migliorando al contempo la scalabilità.

Concetto Chiave: Limitazione Inferiore Ibrida

L'algoritmo sfrutta l'osservazione che su qualsiasi sottodominio specifico (nodo) dello spazio di ricerca, solo un sottoinsieme di punti di addestramento (termini di kernel) influenza significativamente la forma locale della media a posteriori. I termini corrispondenti a punti di addestramento distanti hanno variazioni trascurabili sul nodo.

Il metodo partiziona i termini di kernel in due insiemi basati su una soglia di importanza euristica $\rho$:

1. Termini Importanti ($I(h)$): Termini con grande potenziale influenza sul nodo corrente.
   • Trattamento: Questi sono rilassati utilizzando inviluppi lineari a tratti (PWL) consapevoli del segno su una variabile di distanza scalare (ad esempio, distanza euclidea scalata).
   • Meccanismo: Per i kernel RBF, la variabile di distanza è la distanza quadrata; per i kernel Matérn, è la distanza. Il segno del coefficiente $\alpha_i$ è gestito esplicitamente:
     • Se $\alpha_i > 0$, il limite inferiore utilizza l'inviluppo inferiore PWL del kernel.
     • Se $\alpha_i < 0$, il limite inferiore utilizza l'inviluppo superiore PWL (poiché moltiplicare per un negativo inverte la disuguaglianza).
2. Termini Non Importanti ($U(h)$): Termini con piccola potenziale influenza.
   • Trattamento: Questi sono limitati utilizzando limiti analitici chiusi economici.
   • Meccanismo: Poiché i kernel sono decrescenti monotonicamente con la distanza, i limiti sono derivati semplicemente calcolando le distanze scalate minime e massime dal punto di addestramento all'iperrettangolo del nodo.

Flusso di Lavoro Algoritmico

1. Diramazione a Spazio Ridotto: La diramazione avviene solo sulle variabili decisionali originali $x$, non su variabili ausiliarie.
2. Limite Inferiore del Nodo: Ad ogni nodo, l'algoritmo costruisce un Programma Quadraticamente Vincolato a Numeri Interi Misto (MIQCP). L'obiettivo minimizza la somma dei rilassamenti PWL per i termini importanti e le costanti analitiche per i termini non importanti.
3. Limite Superiore del Nodo: Ottenuto tramite ottimizzazione locale (L-BFGS-B) della media a posteriori esatta all'interno del nodo.
4. Convergenza: L'algoritmo garantisce la convergenza globale $\epsilon$ perché il divario tra i limiti piecewise/analitici e la funzione vera svanisce man mano che il diametro del nodo tende a zero.

3. Contributi Chiave

1. Framework di Limitazione Inferiore Ibrido: Una procedura innovativa che combina rilassamenti lineari a tratti stretti per i termini critici localmente con limiti analitici economici per il resto. Questo evita il collo di bottiglia computazionale del rilassamento di tutti i $N$ termini.
2. Rilassamento Consapevole del Segno: Una formulazione matematica rigorosa che gestisce correttamente i segni misti dei coefficienti del GP ($\alpha_i$) per garantire limiti inferiori validi, il che è cruciale per somme non convesse.
3. Solutore Esatto Scalabile: L'introduzione di PALM-Mean, che fornisce una soluzione globale deterministica per la media a posteriori esatta, colmando il divario tra solutori esatti intrattabili e metodi di approssimazione inesatti.
4. Garanzie Teoriche: Dimostrazione della validità del limite inferiore ibrido e della convergenza globale $\epsilon$ dell'algoritmo di branch-and-bound spaziale.

4. Risultati Sperimentali

Gli autori hanno valutato PALM-Mean rispetto a solutori generici all'avanguardia (SCIP, MAiNGO, BARON) su benchmark sintetici e applicazioni reali.

• Benchmark Sintetici (Funzioni EggHolder e Schwefel):
  • Scalabilità con $N$: All'aumentare del numero di punti di addestramento ($N$) (fino a 1.500), i solutori generici non sono riusciti a risolvere le istanze entro i limiti di tempo o hanno richiesto tempi eccessivi. PALM-Mean ha risolto quasi tutte le istanze, con la versione parallela a 16 core che mostra significativi guadagni di velocità.
  • Scalabilità con la Dimensione: PALM-Mean ha mantenuto prestazioni superiori all'aumentare della dimensione di input, mentre gli altri solutori si sono degradati rapidamente.
  • Dimensione dell'Albero: PALM-Mean ha esplorato ordini di grandezza meno nodi branch-and-bound rispetto a SCIP e MAiNGO, indicando limiti inferiori molto più stretti e una potatura più efficace.
• Applicazioni Reali:
  • Reazione di N-benzilazione: PALM-Mean ha risolto il problema in ~15 secondi (16 core), mentre SCIP ha impiegato ~107 secondi e MAiNGO/BARON hanno raggiunto i limiti di tempo con limiti deboli.
  • Produzione Additiva Autonoma: Su un'istanza più difficile con 100 punti dati, solo PALM-Mean (16 core) e SCIP hanno trovato l'ottimo globale entro il limite di 1 ora. PALM-Mean è stato più veloce e ha utilizzato un albero di ricerca drasticamente più piccolo.

5. Significato e Impatto

• Colmare il Divario: PALM-Mean risolve il vuoto metodologico specifico in cui i metodi esatti esistenti non scalano e i metodi di approssimazione sacrificano la correttezza. Permette l'ottimizzazione globale certificata di surrogati GP addestrati.
• Utilità Pratica: Questo è fondamentale per ambienti scientifici a basso volume di dati (comuni in chimica, scienza dei materiali e ingegneria) dove i GP sono il modello surrogato standard e prendere decisioni globali "sicure" (ad esempio, evitare condizioni operative pericolose) è di primaria importanza.
• Direzioni Future: Gli autori notano che, sebbene il lavoro attuale si concentri sulla media a posteriori, la prospettiva piecewise-analitica potrebbe essere estesa all'ottimizzazione della varianza a posteriori del GP o delle funzioni di acquisizione (come il Lower Confidence Bound), sebbene queste presentino sfide computazionali aggiuntive a causa delle doppie sommatorie.

In sintesi, PALM-Mean rappresenta un avanzamento significativo nell'ottimizzazione basata su surrogati, sfruttando la struttura specifica dei Processi Gaussiani per creare un algoritmo di ottimizzazione globale scalabile, esatto e robusto.