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

以下は、論文「An Efficient Spatial Branch-and-Bound Algorithm for Global Optimization of Gaussian Process Posterior Mean Functions」の詳細な技術的サマリーです。

1. 問題定義

本論文は、コンパクトな超長方体領域における、訓練済みのガウス過程（GP）事後平均関数 $\mu(x)$ の決定論的グローバル最適化を取り扱います。

• 背景: 科学および工学のワークフローにおいて、GP は高価なシミュレーションや実験データに基づいて訓練され、サロゲートモデルとして頻繁に用いられます。訓練後、これらのモデルは設計、制御、較正などの最適化問題に組み込まれ、事後平均の最小化が目標となります。
• 数学的定式化: 事後平均は、訓練点を中心に配置された $N$ 個のカーネル項の重み付き和として表されます：
  $$\mu(x) = \sum_{i=1}^N \alpha_i k_L(x, x_i)$$
  ここで、$\alpha_i$ は訓練データから導出された係数（正負の符号が混在し得る）であり、$k_L$ は定常カーネル（例：RBF、Matérn）です。
• 課題:
  • 非凸性: 関数は非凸で多峰性の重み付き和です。
  • スケーラビリティ: 既存の厳密な決定論的ソルバ（BARON や ANTIGONE など）は、$N$ が増加するにつれて困難に直面します。これらはすべてのカーネル項を同時に緩和する必要があり、これにより緩い下限が生じ、分枝限定木が指数関数的に成長するためです。
  • 近似のトレードオフ: 近似に基づく手法は実用性を向上させますが、修正された問題を解くことになり、正確な事後平均に対するグローバル最適性の保証を失います。

2. 手法：PALM-Mean

著者は、厳密性を保ちながらスケーラビリティを向上させるために設計された、低次元空間における空間的分枝限定アルゴリズムであるPALM-Mean（Piecewise-Analytic Lower-bounding Method：区分的解析的下限法）を提案します。

中核概念：ハイブリッド下限法

このアルゴリズムは、探索空間の任意の特定部分領域（ノード）において、訓練点（カーネル項）のサブセットのみが事後平均の局所的な形状に有意に影響を与えるという観察結果を利用します。遠くの訓練点に対応する項は、そのノード上で無視できるほどの変動しか示しません。

本手法は、ヒューリスティックな重要度閾値 $\rho$ に基づいてカーネル項を 2 つの集合に分割します：

1. 重要な項 ($I(h)$): 現在のノードに大きな潜在的な影響を持つ項。
   • 処理: これらは、スカラー距離変数（例：スケーリングされたユークリッド距離）において、符号を考慮した区分的線形（PWL）エンベロープを用いて緩和されます。
   • メカニズム: RBF カーネルの場合、距離変数は二乗距離です。Matérn カーネルの場合、距離そのものです。係数 $\alpha_i$ の符号は明示的に処理されます：
     • $\alpha_i > 0$ の場合、下限にはカーネルの PWL 下限エンベロープを使用します。
     • $\alpha_i < 0$ の場合、負の数を掛けることで不等号が反転するため、下限には PWL 上限エンベロープを使用します。
2. 重要でない項 ($U(h)$): 潜在的な影響が小さい項。
   • 処理: これらは、安価な閉形式の解析的限界を用いて制限されます。
   • メカニズム: カーネルは距離に対して単調減少であるため、限界は、訓練点からノードの超長方体までのスケーリングされた距離の最小値と最大値を計算するだけで導出されます。

アルゴリズムのワークフロー

1. 低次元空間分枝: 分枝は、補助変数ではなく、元の決定変数 $x$ のみに対して行われます。
2. ノード下限: 各ノードにおいて、アルゴリズムは混合整数二次拘束計画問題（MIQCP）を構築します。目的関数は、重要な項の PWL 緩和の和と、重要でない項の解析的定数の和を最小化します。
3. ノード上限: ノード内の正確な事後平均の局所最適化（L-BFGS-B）によって得られます。
4. 収束: ノードの直径がゼロに近づくにつれて、区分的/解析的限界と真の関数の間のギャップが消失するため、アルゴリズムは $\epsilon$-グローバル収束を保証します。

3. 主要な貢献

1. ハイブリッド下限フレームワーク: 局所的に重要な項に対しては tight な区分的線形緩和を、残りの項に対しては安価な解析的限界を組み合わせる新規手順。これにより、すべての $N$ 項を緩和するという計算上のボトルネックを回避します。
2. 符号を考慮した緩和: GP 係数（$\alpha_i$）の混在する符号を正しく処理し、有効な下限を保証する厳密な数学的定式化。これは非凸和にとって不可欠です。
3. スケーラブルな厳密ソルバ: 正確な事後平均に対する決定論的グローバル解を提供する PALM-Mean の導入。これにより、扱いにくい厳密ソルバと不正確な近似手法の間のギャップを埋めます。
4. 理論的保証: ハイブリッド下限の有効性と、空間的分枝限定アルゴリズムの $\epsilon$-グローバル収束の証明。

4. 実験結果

著者は、合成ベンチマークおよび実世界アプリケーションにおいて、PALM-Mean を最先端の汎用ソルバ（SCIP、MAiNGO、BARON）と比較評価しました。

• 合成ベンチマーク（EggHolder 関数および Schwefel 関数）:
  • $N$ に対するスケーリング: 訓練点の数（$N$）が増加する（最大 1,500）につれて、汎用ソルバは時間制限内でインスタンスを解くことに失敗するか、過度な時間を要しました。PALM-Mean はほぼすべてのインスタンスを解決し、16 コア並列版は顕著な高速化を示しました。
  • 次元に対するスケーリング: 入力次元が増加するにつれて、PALM-Mean は優れた性能を維持しましたが、他のソルバは急速に性能が低下しました。
  • 木サイズ: PALM-Mean は SCIP や MAiNGO に比べて、桁違いに少ない分枝限定ノードを探索しました。これは、はるかに tight な下限と効果的な枝刈りを示しています。
• 実世界アプリケーション:
  • N-ベンジル化反応: PALM-Mean（16 コア）は約 15 秒で問題を解決しましたが、SCIP は約 107 秒を要し、MAiNGO/BARON は弱い限界で時間制限に達しました。
  • 自律型積層造形: 100 データ点を有するより困難なインスタンスにおいて、1 時間以内の時間制限内でグローバル最適解を特定できたのは PALM-Mean（16 コア）と SCIP のみでした。PALM-Mean はより高速であり、劇的に小さな探索木を使用しました。

5. 意義と影響

• ギャップの埋め合わせ: PALM-Mean は、既存の厳密な手法がスケーリングできず、近似手法が正しさを犠牲にするという特定の方法的ギャップを解決します。これにより、訓練された GP サロゲートモデルの認証されたグローバル最適化が可能になります。
• 実用性: これは、化学、材料科学、工学などで一般的である低データ科学設定において重要です。これらの分野では GP が標準的なサロゲートモデルであり、「安全な」グローバル意思決定（例：安全でない運転条件の回避）が極めて重要だからです。
• 将来の方向性: 著者は、現在の研究は事後平均に焦点を当てているが、区分的解析的アプローチは、GP 事後分散や獲得関数（Lower Confidence Bound など）の最適化にも拡張可能であると指摘しています。ただし、これらは二重総和に起因する追加の計算的課題を伴います。

要約すると、PALM-Mean は、ガウス過程の特定の構造を活用して、スケーラブルで厳密かつ堅牢なグローバル最適化アルゴリズムを構築することにより、サロゲートベースの最適化における重要な進歩を表しています。