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

1. Problemstellung

Das Paper adressiert die deterministische globale Optimierung einer trainierten Gauß-Prozess (GP) Posterior-Mittelwertfunktion, $\mu(x)$, über einem kompakten hyperrechteckigen Bereich.

• Kontext: In wissenschaftlichen und ingenieurtechnischen Arbeitsabläufen werden GPs häufig auf teuren Simulations- oder experimentellen Daten trainiert, um als Surrogate zu dienen. Sobald sie trainiert sind, werden diese Modelle in Optimierungsprobleme eingebettet (z. B. Design, Steuerung, Kalibrierung), wobei das Ziel darin besteht, den Posterior-Mittelwert zu minimieren.
• Mathematische Formulierung: Der Posterior-Mittelwert ist eine gewichtete Summe von $N$ Kernel-Termen, die an Trainingspunkten zentriert sind:
  $$\mu(x) = \sum_{i=1}^N \alpha_i k_L(x, x_i)$$
  wobei $\alpha_i$ Koeffizienten sind, die aus den Trainingsdaten abgeleitet werden (die sowohl positive als auch negative Vorzeichen haben können) und $k_L$ ein stationärer Kernel ist (z. B. RBF, Matérn).
• Herausforderungen:
  • Nicht-Konvexität: Die Funktion ist eine nicht-konvexe, multimodale gewichtete Summe.
  • Skalierbarkeit: Bestehende exakte deterministische Löser (wie BARON oder ANTIGONE) haben Schwierigkeiten, wenn $N$ zunimmt, da sie jeden Kernel-Term gleichzeitig relaxieren müssen, was zu schwachen Schranken und einem exponentiellen Wachstum des Branch-and-Bound-Baums führt.
  • Approximations-Abwägung: Approximationsbasierte Methoden verbessern die Handhabbarkeit, lösen jedoch ein modifiziertes Problem und verlieren die Garantie der globalen Optimalität für den exakten Posterior-Mittelwert.

2. Methodik: PALM-Mean

Die Autoren schlagen PALM-Mean (Piecewise-Analytic Lower-bounding Method) vor, einen reduzierten Raum-Spatial-Branch-and-Bound-Algorithmus, der entwickelt wurde, um die Exaktheit zu bewahren und gleichzeitig die Skalierbarkeit zu verbessern.

Kernkonzept: Hybride Untere Schranke

Der Algorithmus nutzt die Beobachtung aus, dass auf einem beliebigen spezifischen Teilbereich (Knoten) des Suchraums nur eine Teilmenge der Trainingspunkte (Kernel-Terme) die lokale Form des Posterior-Mittelwerts signifikant beeinflusst. Terme, die weit entfernten Trainingspunkten entsprechen, weisen über den Knoten hinweg eine vernachlässigbare Variation auf.

Die Methode unterteilt Kernel-Terme basierend auf einem heuristischen Wichtigkeitsschwellenwert $\rho$ in zwei Mengen:

1. Wichtige Terme ($I(h)$): Terme mit großem potenziellem Einfluss auf den aktuellen Knoten.
   • Behandlung: Diese werden unter Verwendung von vorzeichenbewussten stückweise linearen (PWL) Einhüllenden in einer skalaren Distanzvariable (z. B. skalierte euklidische Distanz) relaxiert.
   • Mechanismus: Für RBF-Kernel ist die Distanzvariable die quadrierte Distanz; für Matérn-Kernel ist es die Distanz. Das Vorzeichen des Koeffizienten $\alpha_i$ wird explizit behandelt:
     • Wenn $\alpha_i > 0$, verwendet die untere Schranke die PWL-Untereinheit des Kernels.
     • Wenn $\alpha_i < 0$, verwendet die untere Schranke die PWL-Obereinheit (da Multiplikation mit einer negativen Zahl die Ungleichung umkehrt).
2. Unwichtige Terme ($U(h)$): Terme mit kleinem potenziellem Einfluss.
   • Behandlung: Diese werden unter Verwendung von günstigen, analytischen Schranken in geschlossener Form begrenzt.
   • Mechanismus: Da Kernel monoton mit der Distanz abnehmen, werden die Schranken einfach durch Berechnung der minimalen und maximalen skalierten Distanzen vom Trainingspunkt zum Hyperrechteck des Knotens abgeleitet.

Algorithmischer Ablauf

1. Branching im reduzierten Raum: Das Branching erfolgt nur über die ursprünglichen Entscheidungsvariablen $x$, nicht über Hilfsvariablen.
2. Untere Schranke des Knotens: An jedem Knoten konstruiert der Algorithmus ein gemischt-ganzzahliges quadratisch eingeschränktes Programm (MIQCP). Das Ziel minimiert die Summe der PWL-Relaxationen für wichtige Terme und die analytischen Konstanten für unwichtige Terme.
3. Obere Schranke des Knotens: Wird durch lokale Optimierung (L-BFGS-B) des exakten Posterior-Mittelwerts innerhalb des Knotens ermittelt.
4. Konvergenz: Der Algorithmus garantiert eine $\epsilon$-globale Konvergenz, da die Lücke zwischen den stückweisen/analytischen Schranken und der wahren Funktion verschwindet, wenn der Knotendurchmesser gegen Null geht.

3. Hauptbeiträge

1. Hybrides Rahmenwerk für untere Schranken: Ein neues Verfahren, das enge stückweise lineare Relaxationen für lokal kritische Terme mit kostengünstigen analytischen Schranken für den Rest kombiniert. Dies vermeidet den rechnerischen Engpass des Relaxierens aller $N$ Terme.
2. Vorzeichenbewusste Relaxation: Eine rigorose mathematische Formulierung, die die gemischten Vorzeichen der GP-Koeffizienten ($\alpha_i$) korrekt behandelt, um gültige untere Schranken zu gewährleisten, was für nicht-konvexe Summen entscheidend ist.
3. Skalierbarer exakter Löser: Die Einführung von PALM-Mean, das eine deterministische globale Lösung für den exakten Posterior-Mittelwert liefert und die Lücke zwischen unlösbaren exakten Solvern und ungenauen Approximationsmethoden schließt.
4. Theoretische Garantien: Nachweis der Gültigkeit der hybriden unteren Schranke und der $\epsilon$-globalen Konvergenz des Spatial-Branch-and-Bound-Algorithmus.

4. Experimentelle Ergebnisse

Die Autoren bewerteten PALM-Mean gegenüber state-of-the-art allgemeinen Solvern (SCIP, MAiNGO, BARON) an synthetischen Benchmarks und realen Anwendungen.

• Synthetische Benchmarks (EggHolder- und Schwefel-Funktionen):
  • Skalierung mit $N$: Wenn die Anzahl der Trainingspunkte ($N$) zunahm (bis zu 1.500), versagten allgemeine Solver darin, Instanzen innerhalb der Zeitlimits zu lösen, oder benötigten übermäßige Zeit. PALM-Mean löste nahezu alle Instanzen, wobei die 16-Kern-Parallelversion erhebliche Beschleunigungen zeigte.
  • Skalierung mit der Dimension: PALM-Mean behielt seine überlegene Leistung bei, wenn die Eingabedimension zunahm, während andere Solver schnell an Leistung verloren.
  • Baumgröße: PALM-Mean durchsuchte um Größenordnungen weniger Branch-and-Bound-Knoten im Vergleich zu SCIP und MAiNGO, was auf viel engere untere Schranken und effektivere Pruning-Verfahren hindeutet.
• Reale Anwendungen:
  • N-Benzylations-Reaktion: PALM-Mean löste das Problem in ca. 15 Sekunden (16-Kern), während SCIP ca. 107 Sekunden benötigte und MAiNGO/BARON bei schwachen Schranken die Zeitlimits erreichten.
  • Autonome additive Fertigung: Bei einer schwierigeren Instanz mit 100 Datenpunkten fanden nur PALM-Mean (16-Kern) und SCIP innerhalb des 1-Stunden-Limits das globale Optimum. PALM-Mean war schneller und verwendete einen drastisch kleineren Suchbaum.

5. Bedeutung und Auswirkung

• Schließen der Lücke: PALM-Mean schließt die spezifische methodische Lücke, in der bestehende exakte Methoden nicht skalieren und Approximationsmethoden die Korrektheit opfern. Es ermöglicht eine zertifizierte globale Optimierung trainierter GP-Surrogate.
• Praktischer Nutzen: Dies ist kritisch für wissenschaftliche Szenarien mit geringen Datenmengen (häufig in Chemie, Materialwissenschaft und Ingenieurwesen), in denen GPs das Standard-Surrogatmodell sind und das Treffen "sicherer" globaler Entscheidungen (z. B. Vermeidung unsicherer Betriebsbedingungen) von höchster Priorität ist.
• Zukünftige Richtungen: Die Autoren stellen fest, dass sich die aktuelle Arbeit zwar auf den Posterior-Mittelwert konzentriert, die stückweise-analytische Perspektive jedoch auf die Optimierung der GP-Posterior-Varianz oder Akquisitionsfunktionen (wie Lower Confidence Bound) erweitert werden könnte, obwohl diese aufgrund von doppelten Summationen zusätzliche rechnerische Herausforderungen mit sich bringen.

Zusammenfassend stellt PALM-Mean einen bedeutenden Fortschritt in der surrogate-basierten Optimierung dar, indem es die spezifische Struktur von Gauß-Prozessen nutzt, um einen skalierbaren, exakten und robusten Algorithmus zur globalen Optimierung zu schaffen.