Bayesian Optimization

Idea

A sequential approach for efficient global optimization

• Function to optimize
• Space to optimize: parameters to explore
• Bayesian model: provides prediction and uncertainity
• Acquisition function: tradeoff between exploration and exploitation

Pseudocode

• Set a termination criteria (budgets, iterations, maxima)
• Evaluate $f(x)$ on initial set of points
• While criteria is not met:
  • update surrogate model on all data
  • Optimize acquisition function to find a maxima
  • Evaluate $f(x_{new})$

The surrogate model: a probabilistic model (e.g., Gaussian Process) that approximates the true objective function based on observed data. It provides both a prediction of the function value at any given point and an estimate of the uncertainty of that prediction. This model outputs both a predicted mean and a variance, which are used to guide the optimization process.

The acquisition function: a function that uses the surrogate model’s predictions to determine the next point to evaluate. It balances exploration (sampling points where the surrogate model is uncertain) and exploitation (sampling points where the surrogate model predicts a low function value). Common acquisition functions include Expected Improvement, Probability of Improvement, and Upper Confidence Bound.

import numpy as np
from scipy.optimize import minimize
 
def bayesian_optimization(f, bounds, n_iter=25, n_init=5):
    # Step 1: Initialize with random points
    X = np.random.uniform(bounds[:, 0], bounds[:, 1], (n_init, bounds.shape[0]))
    y = np.array([f(x) for x in X])
    
    for _ in range(n_iter):
        # Step 2: Fit surrogate model (e.g., Gaussian Process)
        model = fit_surrogate_model(X, y)
        
        # Step 3: Optimize acquisition function to find next point
        x_next = optimize_acquisition_function(model, bounds)
        
        # Step 4: Evaluate the objective function at the new point
        y_next = f(x_next)
        
        # Step 5: Update data
        X = np.vstack((X, x_next))
        y = np.append(y, y_next)
    
    return X[np.argmin(y)], np.min(y)