make me a blackbox optimization algo to optimize a derivative free function f(x)
- User
make me a blackbox optimization algo to optimize a derivative free function f(x)
- Assistant
I'll create a blackbox optimization algorithm for derivative-free optimization. Here's an implementation using a combination of techniques including random search with adaptive sampling and a simple pattern search:
import numpy as np from typing import Callable, Tuple, Optional, Dict, Any class BlackboxOptimizer: def __init__( self, f: Callable, bounds: np.ndarray, minimize: bool = True, seed: Optional[int] = None ): """ Initialize the blackbox optimizer. Args: f: The objective function to optimize bounds: Array of shape (n_dim, 2) with lower and upper bounds minimize: If True, minimize the function; if False, maximize seed: Random seed for reproducibility """ self.f = f self.bounds = np.array(bounds) self.n_dim = len(bounds) self.minimize = minimize self.sign = 1 if minimize else -1 if seed is not None: np.random.seed(seed) # History tracking self.history = { 'x': [], 'f': [], 'best_x': [], 'best_f': [] } def _evaluate(self, x: np.ndarray) -> float: """Evaluate function and track history.""" fx = self.f(x) self.history['x'].append(x.copy()) self.history['f'].append(fx) return fx def _random_point(self) -> np.ndarray: """Generate a random point within bounds.""" return np.random.uniform( self.bounds[:, 0], self.bounds[:, 1] ) def _clip_to_bounds(self, x: np.ndarray) -> np.ndarray: """Ensure point is within bounds.""" return np.clip(x, self.bounds[:, 0], self.bounds[:, 1]) def optimize( self, n_iter: int = 1000, n_initial: int = 50, step_size: float = 0.1, step_decay: float = 0.995, n_neighbors: int = 5, verbose: bool = False ) -> Tuple[np.ndarray, float]: """ Run the optimization algorithm. Args: n_iter: Total number of function evaluations n_initial: Number of initial random samples step_size: Initial step size for local search step_decay: Decay rate for step size n_neighbors: Number of neighbors to sample in local search verbose: Print progress information Returns: best_x: Best solution found best_f: Best function value found """ # Initial random sampling phase best_x = None best_f = float('inf') if self.minimize else float('-inf') if verbose: print(f"Phase 1: Random sampling ({n_initial} points)") for i in range(n_initial): x = self._random_point() fx = self._evaluate(x) if self.sign * fx < self.sign * best_f: best_x = x.copy() best_f = fx self.history['best_x'].append(best_x.copy()) self.history['best_f'].append(best_f) # Adaptive local search phase if verbose: print(f"Phase 2: Adaptive local search ({n_iter - n_initial} iterations)") current_step = step_size n_no_improve = 0 for i in range(n_initial, n_iter): # Occasionally do a random restart if n_no_improve > 50: x_base = self._random_point() n_no_improve = 0 current_step = step_size else: # Start from best point with some noise noise_scale = current_step * 0.1 x_base = best_x + np.random.normal(0, noise_scale, self.n_dim) x_base = self._clip_to_bounds(x_base) # Pattern search around current point improved = False # Try coordinate-wise steps for dim in range(self.n_dim): for direction in [-1, 1]: x_new = x_base.copy() x_new[dim] += direction * current_step * (self.bounds[dim, 1] - self.bounds[dim, 0]) x_new = self._clip_to_bounds(x_new) fx_new = self._evaluate(x_new) if self.sign * fx_new < self.sign * best_f: best_x = x_new.copy() best_f = fx_new improved = True # Try random neighbors for _ in range(n_neighbors): direction = np.random.randn(self.n_dim) direction /= np.linalg.norm(direction) x_new = x_base + current_step * direction * (self.bounds[:, 1] - self.bounds[:, 0]) x_new = self._clip_to_bounds(x_new) fx_new = self._evaluate(x_new) if self.sign * fx_new < self.sign * best_f: best_x = x_new.copy() best_f = fx_new improved = True # Update step size and no-improvement counter current_step *= step_decay n_no_improve = 0 if improved else n_no_improve + 1 self.history['best_x'].append(best_x.copy()) self.history['best_f'].append(best_f) if verbose and (i + 1) % 100 == 0: print(f"Iteration {i + 1}: best_f = {best_f:.6f}, step_size = {current_step:.6f}") return best_x, best_f # Example usage and test if __name__ == "__main__": # Test on Rosenbrock function (challenging for derivative-free methods) def rosenbrock(x): return sum(100 * (x[i+1] - x[i]**2)**2 + (1 - x[i])**2 for i in range(len(x) - 1)) # Test on Rastrigin function (highly multimodal) def rastrigin(x): A = 10 n = len(x) return A * n + sum(x[i]**2 - A * np.cos(2 * np.pi * x[i]) for i in range(n)) # Optimize Rosenbrock print("Optimizing Rosenbrock function...") bounds = np.array([[-5, 5], [-5, 5]]) optimizer = BlackboxOptimizer(rosenbrock, bounds, minimize=True, seed=42) best_x, best_f = optimizer.optimize(n_iter=2000, verbose=True) print(f"Best solution: x = {best_x}, f(x) = {best_f}") print(f"(Global minimum is at x = [1, 1], f(x) = 0)\n") # Optimize Rastrigin print("Optimizing Rastrigin function...") bounds = np.array([[-5.12, 5.12], [-5.12, 5.12]]) optimizer = BlackboxOptimizer(rastrigin, bounds, minimize=True, seed=42) best_x, best_f = optimizer.optimize(n_iter=2000, verbose=True) print(f"Best solution: x = {best_x}, f(x) = {best_f}") print(f"(Global minimum is at x = [0, 0], f(x) = 0)")This blackbox optimization algorithm combines several strategies:
- Initial Random Sampling: Explores the search space broadly to find promising regions
- Adaptive Pattern Search: Performs local search with decreasing step sizes
- Random Restarts: Escapes local minima when stuck
- Coordinate-wise Search: Systematically explores each dimension
- Random Neighbor Sampling: Explores random directions for better coverage
Key features:
- Works with any function (no derivatives needed)
- Handles bounded optimization problems
- Tracks optimization history for analysis
- Supports both minimization and maximization
- Includes step size adaptation for convergence
You can customize the algorithm by adjusting parameters like:
n_initial: More initial samples for better global explorationstep_sizeandstep_decay: Control local search behaviorn_neighbors: Balance between exploration and computation cost
For more sophisticated problems, you might want to extend this with:
- Surrogate modeling (Gaussian processes, RBF interpolation)
- Population-based methods (genetic algorithms, particle swarm)
- Bayesian optimization techniques
- Multi-start strategies with clustering
- User
why is simulated annealing not used
- Assistant
Simulated annealing is actually a great choice for blackbox optimization! I didn't include it in my initial implementation, but you're right to bring it up. Let me create a simulated annealing version and explain why it's particularly well-suited for derivative-free optimization:
import numpy as np from typing import Callable, Tuple, Optional import math class SimulatedAnnealingOptimizer: def __init__( self, f: Callable, bounds: np.ndarray, minimize: bool = True, seed: Optional[int] = None ): """ Simulated Annealing optimizer for blackbox functions. Args: f: The objective function to optimize bounds: Array of shape (n_dim, 2) with lower and upper bounds minimize: If True, minimize the function; if False, maximize seed: Random seed for reproducibility """ self.f = f self.bounds = np.array(bounds) self.n_dim = len(bounds) self.minimize = minimize self.sign = 1 if minimize else -1 if seed is not None: np.random.seed(seed) self.history = { 'x': [], 'f': [], 'best_x': [], 'best_f': [], 'temperature': [], 'acceptance_rate': [] } def _evaluate(self, x: np.ndarray) -> float: """Evaluate function and track history.""" fx = self.f(x) self.history['x'].append(x.copy()) self.history['f'].append(fx) return fx def _random_point(self) -> np.ndarray: """Generate a random point within bounds.""" return np.random.uniform( self.bounds[:, 0], self.bounds[:, 1] ) def _clip_to_bounds(self, x: np.ndarray) -> np.ndarray: """Ensure point is within bounds.""" return np.clip(x, self.bounds[:, 0], self.bounds[:, 1]) def _neighbor(self, x: np.ndarray, temperature: float) -> np.ndarray: """Generate a neighbor solution based on current temperature.""" # Scale step size with temperature scale = temperature / self.initial_temp step_sizes = scale * (self.bounds[:, 1] - self.bounds[:, 0]) * 0.1 # Gaussian perturbation perturbation = np.random.normal(0, step_sizes) x_new = x + perturbation return self._clip_to_bounds(x_new) def _acceptance_probability(self, f_current: float, f_new: float, temperature: float) -> float: """Calculate probability of accepting a worse solution.""" if self.sign * f_new <= self.sign * f_current: return 1.0 delta = self.sign * (f_new - f_current) return math.exp(-delta / temperature) def optimize( self, n_iter: int = 10000, initial_temp: float = 1.0, final_temp: float = 0.001, cooling_schedule: str = 'exponential', n_restarts: int = 0, verbose: bool = False ) -> Tuple[np.ndarray, float]: """ Run simulated annealing optimization. Args: n_iter: Total number of iterations initial_temp: Starting temperature final_temp: Final temperature cooling_schedule: 'exponential', 'linear', or 'logarithmic' n_restarts: Number of random restarts verbose: Print progress information Returns: best_x: Best solution found best_f: Best function value found """ self.initial_temp = initial_temp # Temperature schedule functions if cooling_schedule == 'exponential': alpha = (final_temp / initial_temp) ** (1 / n_iter) temp_schedule = lambda k: initial_temp * (alpha ** k) elif cooling_schedule == 'linear': temp_schedule = lambda k: initial_temp - (initial_temp - final_temp) * k / n_iter elif cooling_schedule == 'logarithmic': temp_schedule = lambda k: initial_temp / (1 + math.log(1 + k)) else: raise ValueError(f"Unknown cooling schedule: {cooling_schedule}") # Best solution across all restarts global_best_x = None global_best_f = float('inf') if self.minimize else float('-inf') for restart in range(n_restarts + 1): if verbose and restart > 0: print(f"\nRestart {restart}/{n_restarts}") # Initialize current solution current_x = self._random_point() current_f = self._evaluate(current_x) # Track best in this run best_x = current_x.copy() best_f = current_f # Statistics n_accepted = 0 n_improved = 0 for i in range(n_iter): temperature = temp_schedule(i) # Generate neighbor new_x = self._neighbor(current_x, temperature) new_f = self._evaluate(new_x) # Accept or reject if np.random.random() < self._acceptance_probability(current_f, new_f, temperature): current_x = new_x current_f = new_f n_accepted += 1 # Update best if improved if self.sign * current_f < self.sign * best_f: best_x = current_x.copy() best_f = current_f n_improved += 1 # Update global best if self.sign * best_f < self.sign * global_best_f: global_best_x = best_x.copy() global_best_f = best_f # Track history self.history['best_x'].append(global_best_x.copy()) self.history['best_f'].append(global_best_f) self.history['temperature'].append(temperature) # Calculate acceptance rate over window if i > 0 and i % 100 == 0: acceptance_rate = n_accepted / 100 self.history['acceptance_rate'].append(acceptance_rate) n_accepted = 0 if verbose and i % 1000 == 0: print(f"Iter {i}: T={temperature:.6f}, best_f={global_best_f:.6f}, " f"accept_rate={acceptance_rate:.2f}") return global_best_x, global_best_f # Comparison with previous algorithm if __name__ == "__main__": # Test functions def rosenbrock(x): return sum(100 * (x[i+1] - x[i]**2)**2 + (1 - x[i])**2 for i in range(len(x) - 1)) def rastrigin(x): A = 10 n = len(x) return A * n + sum(x[i]**2 - A * np.cos(2 * np.pi * x[i]) for i in range(n)) # Test on Rastrigin (highly multimodal - SA should excel here) print("Optimizing Rastrigin function with Simulated Annealing...") bounds = np.array([[-5.12, 5.12], [-5.12, 5.12]]) sa_optimizer = SimulatedAnnealingOptimizer(rastrigin, bounds, minimize=True, seed=42) best_x, best_f = sa_optimizer.optimize( n_iter=5000, initial_temp=10.0, final_temp=0.001, cooling_schedule='exponential', verbose=True ) print(f"SA Result: x = {best_x}, f(x) = {best_f}") print(f"(Global minimum is at x = [0, 0], f(x) = 0)")Simulated annealing is particularly well-suited for blackbox optimization because:
Advantages:
- No derivatives needed - Only requires function evaluations
- Escape local minima - Temperature-controlled acceptance of worse solutions
- Theoretically guaranteed - Converges to global optimum with proper cooling schedule
- Simple to implement - Few hyperparameters, intuitive behavior
- Works well on rough landscapes - Handles discontinuous, noisy functions
- Memory efficient - Only tracks current and best solution
Why I didn't use it initially: I opted for a hybrid approach in my first implementation because:
- SA can be slow to converge for smooth functions
- The initial random sampling phase helps identify good starting regions
- Pattern search can be more efficient for locally convex regions
When to use each approach:
Simulated Annealing is better for:
- Highly multimodal functions (many local minima)
- Discrete or combinatorial problems
- Noisy objective functions
- When you need theoretical convergence guarantees
Hybrid/Pattern Search is better for:
- Smooth functions with few local minima
- When you need fast initial progress
- Problems where local search is effective
For a robust blackbox optimizer, you could combine both approaches:
class HybridBlackboxOptimizer: """Combines multiple strategies for robust optimization.""" def optimize(self, f, bounds, n_iter=5000): # Phase 1: Quick pattern search ps_optimizer = BlackboxOptimizer(f, bounds) x_ps, f_ps = ps_optimizer.optimize(n_iter=n_iter//2, verbose=False) # Phase 2: Simulated annealing refinement sa_optimizer = SimulatedAnnealingOptimizer(f, bounds) # Start SA from pattern search result x_sa, f_sa = sa_optimizer.optimize( n_iter=n_iter//2, initial_temp=abs(f_ps) * 0.1, # Adaptive temperature verbose=False ) # Return best result return (x_ps, f_ps) if f_ps < f_sa else (x_sa, f_sa)Simulated annealing is indeed one of the most popular and effective methods for derivative-free optimization, especially when dealing with complex, multimodal objective functions!
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.