🔢 mathematics

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

This paper introduces PALM-Mean, a scalable deterministic global optimization algorithm for Gaussian process posterior mean functions that combines reduced-space spatial branch-and-bound with a hybrid piecewise-linear and analytic bounding strategy to efficiently handle large datasets while ensuring $\varepsilon$ -global convergence.

Original authors: Wei-Ting Tang, Akshay Kudva, Calvin Tsay, Joel A. Paulson

Published 2026-05-05

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wei-Ting Tang, Akshay Kudva, Calvin Tsay, Joel A. Paulson

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a very smart, but slightly chaotic, weather forecaster. This forecaster (called a Gaussian Process) has studied thousands of past weather reports (training data) and can now predict the weather for any location you ask. However, the forecaster doesn't just give you a single number; it gives you a complex, wiggly map of probabilities.

Your goal is to find the absolute best spot on this map—say, the location with the lowest chance of rain. This is a "global optimization" problem.

The problem is that this map is incredibly complicated. It's built by adding up thousands of tiny, wiggly curves, one for every single piece of data the forecaster learned from. If you try to find the lowest point by just looking at the whole map at once, it's like trying to find the deepest valley in a mountain range that has a million tiny hills and dips. It's too messy for standard math tools to solve quickly, especially if you have a lot of data.

The Old Ways: The "Brute Force" and the "Shortcut"

The paper explains that scientists have tried two main ways to solve this:

The "Brute Force" Approach: You try to analyze every single wiggly curve on the map at the same time.
- The Analogy: Imagine trying to navigate a maze by checking every single wall, corner, and dead end simultaneously. As the maze gets bigger (more data), you get stuck. The computer runs out of time and memory before it can find the exit.
The "Shortcut" Approach: You smooth out the map, turning the wiggly curves into simple straight lines to make it easier to solve.
- The Analogy: This is like looking at a rough, rocky terrain and pretending it's a flat, smooth hill. It's easy to find the bottom of a smooth hill, but you might miss the actual deepest hole because you smoothed it over. You get an answer, but it might not be the true best answer.

The New Solution: PALM-Mean

The authors of this paper, led by Wei-Ting Tang and colleagues, created a new method called PALM-Mean. Think of it as a smart, hybrid navigation strategy that combines the best of both worlds without the downsides.

Here is how it works, using a creative analogy:

1. The "Spotlight" Strategy (Local Importance)

Imagine you are in a dark room with a million tiny lightbulbs (the data points). Most of them are far away and dim. Only a few are right next to you, shining brightly.

Old Way: You try to calculate the exact brightness of every lightbulb in the room to figure out where you are standing.
PALM-Mean: It puts a spotlight on the few lightbulbs right next to you. It analyzes those bright, nearby ones with extreme precision. For the thousands of dim, distant lightbulbs, it just uses a quick, rough estimate because they don't really matter for your immediate location.

2. The "Hybrid Map" (Piecewise-Analytic)

The method builds a map for the computer to search:

For the "Important" nearby data: It draws a detailed, jagged, piece-by-piece map (like a puzzle) that perfectly captures the wiggles and curves. This ensures the answer is exact.
For the "Unimportant" distant data: It draws a simple, smooth box around them. This is fast to calculate and doesn't slow down the computer.

3. The "Search and Prune" (Branch-and-Bound)

The algorithm acts like a detective searching a large building for a lost item.

It divides the building into smaller rooms (nodes).
In each room, it uses its Hybrid Map to guess the lowest possible point.
If the guess says, "Even the lowest point in this room is worse than what we already found," it closes the door on that room and never looks inside again.
Because the "Hybrid Map" is so much smarter than the old "Brute Force" map, the detective can close doors much earlier, saving huge amounts of time.

Why It Matters (According to the Paper)

The paper tested this method on two types of problems:

Fake Math Mountains: They created difficult, wiggly mathematical landscapes with different numbers of data points (from 100 to 1,500).
Real-World Labs: They used real data from chemical reactions (making a specific type of amine) and 3D printing (optimizing print settings).

The Results:

Speed: PALM-Mean was significantly faster than the best existing "Brute Force" computers (like BARON and SCIP).
Scalability: As the number of data points grew, the old methods slowed down to a crawl or gave up entirely. PALM-Mean kept running smoothly.
Accuracy: Unlike the "Shortcut" methods, PALM-Mean guarantees it found the true best answer, not just a good approximation.

The Bottom Line

The paper claims that PALM-Mean is a breakthrough because it stops trying to do everything perfectly all at once. Instead, it intelligently decides where to spend its energy. It focuses its heavy math on the data that actually matters for the current location and ignores the rest with a quick estimate. This allows it to solve complex, real-world optimization problems that were previously too slow or too difficult to solve exactly.

Note: The paper focuses strictly on finding the best settings for these mathematical models. It does not claim to cure diseases or directly control robots, but rather provides a faster, more reliable way to find the "best answer" inside the mathematical models that scientists use for those tasks.

1. Problem Statement

The paper addresses the deterministic global optimization of a trained Gaussian Process (GP) posterior mean function, $\mu(x)$ , over a compact hyperrectangular domain.

Context: In scientific and engineering workflows, GPs are often trained on expensive simulation or experimental data to serve as surrogates. Once trained, these models are embedded into optimization problems (e.g., design, control, calibration) where the goal is to minimize the posterior mean.
Mathematical Formulation: The posterior mean is a weighted sum of $N$ kernel terms centered at training points:
$\mu(x) = \sum_{i=1}^N \alpha_i k_L(x, x_i)$
where $\alpha_i$ are coefficients derived from the training data (which can have mixed positive and negative signs) and $k_L$ is a stationary kernel (e.g., RBF, Matérn).
Challenges:
- Non-convexity: The function is a non-convex, multi-modal weighted sum.
- Scalability: Existing exact deterministic solvers (like BARON or ANTIGONE) struggle as $N$ increases because they must relax every kernel term simultaneously, leading to weak bounds and exponential growth in the branch-and-bound tree.
- Approximation Trade-off: Approximation-based methods improve tractability but solve a modified problem, losing the guarantee of global optimality for the exact posterior mean.

2. Methodology: PALM-Mean

The authors propose PALM-Mean (Piecewise-Analytic Lower-bounding Method), a reduced-space spatial branch-and-bound algorithm designed to preserve exactness while improving scalability.

Core Concept: Hybrid Lower Bounding

The algorithm exploits the observation that on any specific subdomain (node) of the search space, only a subset of training points (kernel terms) significantly influences the local shape of the posterior mean. Terms corresponding to distant training points have negligible variation over the node.

The method partitions kernel terms into two sets based on a heuristic importance threshold $\rho$ :

Important Terms ( $I(h)$ ): Terms with large potential influence on the current node.
- Treatment: These are relaxed using sign-aware piecewise-linear (PWL) envelopes in a scalar distance variable (e.g., scaled Euclidean distance).
- Mechanism: For RBF kernels, the distance variable is squared distance; for Matérn kernels, it is the distance. The sign of the coefficient $\alpha_i$ $α_{i}$ is explicitly handled:
  - If $\alpha_i > 0$ , the lower bound uses the PWL lower envelope of the kernel.
  - If $\alpha_i < 0$ , the lower bound uses the PWL upper envelope (since multiplying by a negative flips the inequality).
Unimportant Terms ( $U(h)$ ): Terms with small potential influence.
- Treatment: These are bounded using cheap, closed-form analytical bounds.
- Mechanism: Since kernels are monotonically decreasing with distance, the bounds are derived simply by calculating the minimum and maximum scaled distances from the training point to the node's hyperrectangle.

Algorithmic Workflow

Reduced-Space Branching: Branching occurs only on the original decision variables $x$ , not on auxiliary variables.
Node Lower Bound: At each node, the algorithm constructs a Mixed-Integer Quadratically Constrained Program (MIQCP). The objective minimizes the sum of the PWL relaxations for important terms and the analytical constants for unimportant terms.
Node Upper Bound: Obtained via local optimization (L-BFGS-B) of the exact posterior mean within the node.
Convergence: The algorithm guarantees $\epsilon$ -global convergence because the gap between the piecewise/analytical bounds and the true function vanishes as the node diameter approaches zero.

3. Key Contributions

Hybrid Lower-Bounding Framework: A novel procedure that combines tight piecewise-linear relaxations for locally critical terms with inexpensive analytical bounds for the rest. This avoids the computational bottleneck of relaxing all $N$ terms.
Sign-Aware Relaxation: A rigorous mathematical formulation that correctly handles the mixed signs of the GP coefficients ( $\alpha_i$ ) to ensure valid lower bounds, which is crucial for non-convex sums.
Scalable Exact Solver: The introduction of PALM-Mean, which provides a deterministic global solution for the exact posterior mean, bridging the gap between intractable exact solvers and inexact approximation methods.
Theoretical Guarantees: Proof of the validity of the hybrid lower bound and the $\epsilon$ -global convergence of the spatial branch-and-bound algorithm.

4. Experimental Results

The authors evaluated PALM-Mean against state-of-the-art general-purpose solvers (SCIP, MAiNGO, BARON) on synthetic benchmarks and real-world applications.

Synthetic Benchmarks (EggHolder & Schwefel functions):
- Scaling with $N$ : As the number of training points ( $N$ ) increased (up to 1,500), general-purpose solvers failed to solve instances within time limits or required excessive time. PALM-Mean solved nearly all instances, with the 16-core parallel version showing significant speedups.
- Scaling with Dimension: PALM-Mean maintained superior performance as input dimension increased, whereas other solvers degraded rapidly.
- Tree Size: PALM-Mean explored orders of magnitude fewer branch-and-bound nodes compared to SCIP and MAiNGO, indicating much tighter lower bounds and more effective pruning.
Real-World Applications:
- N-benzylation Reaction: PALM-Mean solved the problem in ~15 seconds (16-core), while SCIP took ~107 seconds and MAiNGO/BARON hit time limits with weak bounds.
- Autonomous Additive Manufacturing: On a harder instance with 100 data points, only PALM-Mean (16-core) and SCIP found the global optimum within the 1-hour limit. PALM-Mean was faster and used a drastically smaller search tree.

5. Significance and Impact

Bridging the Gap: PALM-Mean solves the specific methodological gap where existing exact methods do not scale, and approximation methods sacrifice correctness. It allows for certified global optimization of trained GP surrogates.
Practical Utility: This is critical for low-data scientific settings (common in chemistry, materials science, and engineering) where GPs are the standard surrogate model, and making "safe" global decisions (e.g., avoiding unsafe operating conditions) is paramount.
Future Directions: The authors note that while the current work focuses on the posterior mean, the piecewise-analytic perspective could be extended to optimizing GP posterior variance or acquisition functions (like Lower Confidence Bound), though these present additional computational challenges due to double summations.

In summary, PALM-Mean represents a significant advancement in surrogate-based optimization by leveraging the specific structure of Gaussian Processes to create a scalable, exact, and robust global optimization algorithm.