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

1. Probleemstelling

Het paper behandelt de deterministische globale optimalisatie van een getrainde posterior-middelfunctie van een Gaussisch Proces (GP), $\mu(x)$, over een compact hyperrechthoekig domein.

• Context: In wetenschappelijke en technische workflows worden GPs vaak getraind op dure simulatie- of experimentele data om als surrogate te dienen. Eenmaal getraind, worden deze modellen ingebed in optimalisatieproblemen (bijv. ontwerp, regeling, kalibratie) waarbij het doel is om de posterior-middelfunctie te minimaliseren.
• Wiskundige Formulering: De posterior-middelfunctie is een gewogen som van $N$ kerntermen gecentreerd rond trainingspunten:
  $$\mu(x) = \sum_{i=1}^N \alpha_i k_L(x, x_i)$$
  waarbij $\alpha_i$ coëfficiënten zijn afgeleid van de trainingsdata (die gemengde positieve en negatieve tekens kunnen hebben) en $k_L$ een stationaire kern is (bijv. RBF, Matérn).
• Uitdagingen:
  • Niet-convexiteit: De functie is een niet-convexe, multimodale gewogen som.
  • Schaalbaarheid: Bestaande exacte deterministische solvers (zoals BARON of ANTIGONE) hebben moeite naarmate $N$ toeneemt, omdat ze elke kernterm gelijktijdig moeten relaxeren, wat leidt tot zwakke ondergrenzen en een exponentiële groei van de branch-and-bound-boom.
  • Trade-off bij Benadering: Benaderingsmethoden verbeteren de hanteerbaarheid, maar lossen een gewijzigd probleem op, waardoor de garantie op globale optimaliteit voor de exacte posterior-middelfunctie verloren gaat.

2. Methodologie: PALM-Mean

De auteurs stellen PALM-Mean (Piecewise-Analytic Lower-bounding Method) voor, een reduced-space spatial branch-and-bound-algoritme dat is ontworpen om exactheid te behouden terwijl de schaalbaarheid wordt verbeterd.

Kernconcept: Hybride Ondergrens

Het algoritme maakt gebruik van de observatie dat op elk specifiek subdomein (knooppunt) van de zoekruimte slechts een subset van trainingspunten (kerntermen) de lokale vorm van de posterior-middelfunctie significant beïnvloedt. Termen die corresponderen met verre trainingspunten hebben een verwaarloosbare variatie over het knooppunt.

De methode partitioneert kerntermen in twee sets op basis van een heuristische belangrijkheidsdrempel $\rho$:

1. Belangrijke Termen ($I(h)$): Termen met grote potentiële invloed op het huidige knooppunt.
   • Behandeling: Deze worden relaxed met behulp van tekenbewuste stuksgewijs lineaire (PWL) omhullenden in een scalair afstandsvariabele (bijv. geschaalde Euclidische afstand).
   • Mechanisme: Voor RBF-kernen is de afstandsvariabele de kwadratische afstand; voor Matérn-kernen is het de afstand. Het teken van de coëfficiënt $\alpha_i$ wordt expliciet verwerkt:
     • Als $\alpha_i > 0$, gebruikt de ondergrens de PWL-onderomhullende van de kern.
     • Als $\alpha_i < 0$, gebruikt de ondergrens de PWL-bovenomhullende (aangezien vermenigvuldiging met een negatief getal de ongelijkheid omkeert).
2. Onbelangrijke Termen ($U(h)$): Termen met kleine potentiële invloed.
   • Behandeling: Deze worden begrensd met behulp van goedkope, gesloten-formule analytische grenzen.
   • Mechanisme: Omdat kernen monotoon afnemen met de afstand, worden de grenzen eenvoudig afgeleid door de minimum- en maximum-geschaalde afstanden van het trainingspunt tot het hyperrechthoek van het knooppunt te berekenen.

Algorithmische Werkwijze

1. Reduced-Space Branching: Branching vindt alleen plaats op de originele beslissingsvariabelen $x$, niet op hulpvariabelen.
2. Knooppunt-Ondergrens: Bij elk knooppunt construeert het algoritme een Mixed-Integer Quadratically Constrained Program (MIQCP). De doelstelling minimaliseert de som van de PWL-relaxaties voor belangrijke termen en de analytische constanten voor onbelangrijke termen.
3. Knooppunt-Bovengrens: Verkregen via lokale optimalisatie (L-BFGS-B) van de exacte posterior-middelfunctie binnen het knooppunt.
4. Convergentie: Het algoritme garandeert $\epsilon$-globale convergentie omdat de kloof tussen de stuksgewijs/analytische grenzen en de ware functie verdwijnt naarmate de knooppunt-diameter naar nul nadert.

3. Belangrijkste Bijdragen

1. Hybride Ondergrens-Framework: Een nieuwe procedure die strakke stuksgewijs lineaire relaxaties voor lokaal kritieke termen combineert met goedkope analytische grenzen voor de rest. Dit vermijdt de computatieflesnek van het relaxeren van alle $N$ termen.
2. Tekenbewuste Relaxatie: Een rigoureuze wiskundige formulering die correct omgaat met de gemengde tekens van de GP-coëfficiënten ($\alpha_i$) om geldige ondergrenzen te garanderen, wat cruciaal is voor niet-convexe sommen.
3. Schaalbare Exacte Solver: De introductie van PALM-Mean, die een deterministische globale oplossing biedt voor de exacte posterior-middelfunctie, en zo de kloof overbrugt tussen onhanteerbare exacte solvers en onnauwkeurige benaderingsmethoden.
4. Theoretische Garanties: Bewijs van de geldigheid van de hybride ondergrens en de $\epsilon$-globale convergentie van het spatial branch-and-bound-algoritme.

4. Experimentele Resultaten

De auteurs hebben PALM-Mean geëvalueerd tegen state-of-the-art algemene solvers (SCIP, MAiNGO, BARON) op synthetische benchmarks en real-world toepassingen.

• Synthetische Benchmarks (EggHolder & Schwefel functies):
  • Schaalbaarheid met $N$: Naarmate het aantal trainingspunten ($N$) toenam (tot 1.500), faalden algemene solvers om instanties binnen tijdslimieten op te lossen of vereisten ze excessive tijd. PALM-Mean loste bijna alle instanties op, waarbij de 16-core parallelle versie aanzienlijke snelheidswinsten liet zien.
  • Schaalbaarheid met Dimensie: PALM-Mean behield superieure prestaties naarmate de invoerdimensie toenam, terwijl andere solvers snel degradeerden.
  • Boomgrootte: PALM-Mean onderzocht orde van grootte minder branch-and-bound-knooppunten in vergelijking met SCIP en MAiNGO, wat wijst op veel strakkere ondergrenzen en effectiever pruning.
• Real-World Toepassingen:
  • N-benzylering Reactie: PALM-Mean loste het probleem op in ~15 seconden (16-core), terwijl SCIP ~107 seconden nodig had en MAiNGO/BARON tijdslimieten bereikten met zwakke grenzen.
  • Autonome Additieve Fabricage: Op een moeilijkere instantie met 100 datapunten vonden alleen PALM-Mean (16-core) en SCIP de globale optimum binnen het 1-uurs limiet. PALM-Mean was sneller en gebruikte een drastisch kleinere zoekboom.

5. Betekenis en Impact

• Overbrugging van de Kloof: PALM-Mean lost de specifieke methodologische kloof op waar bestaande exacte methoden niet schalen en benaderingsmethoden correctheid opofferen. Het maakt gecertificeerde globale optimalisatie van getrainde GP-surrogates mogelijk.
• Praktisch Nut: Dit is cruciaal voor wetenschappelijke settings met weinig data (vaak voorkomend in chemie, materiaalkunde en engineering) waar GPs het standaard surrogate-model zijn en het maken van "veilige" globale beslissingen (bijv. het vermijden van onveilige bedrijfsomstandigheden) van het grootste belang is.
• Toekomstige Richtingen: De auteurs merken op dat hoewel het huidige werk zich richt op de posterior-middelfunctie, het stuksgewijs-analytische perspectief kan worden uitgebreid naar het optimaliseren van de GP-posterior-variatie of acquisitiefuncties (zoals Lower Confidence Bound), hoewel deze extra computationele uitdagingen met zich meebrengen door dubbele sommaties.

Kortom, PALM-Mean vertegenwoordigt een aanzienlijke vooruitgang in surrogate-gebaseerde optimalisatie door gebruik te maken van de specifieke structuur van Gaussische Processen om een schaalbaar, exact en robuust globaal optimalisatie-algoritme te creëren.