Global Search Algorithms

Global search algorithms are designed to explore the entire search space rather than focusing on a single neighborhood. They are better at avoiding local optima but may be slower to converge to the exact optimum.

Overview

Algorithm	Description
Random Search	Pure random sampling. Simple but effective baseline.
Grid Search	Systematic traversal of the search space.
Random Restart Hill Climbing	Hill climbing with periodic random restarts.
Random Annealing	Large initial steps that gradually decrease.
Pattern Search	Structured exploration using geometric patterns.
Powell’s Method	Sequential optimization along each dimension.
Lipschitz Optimizer	Uses Lipschitz continuity bounds to prune search.
DIRECT Algorithm	Divides space into regions, exploring the most promising.

When to Use Global Search

Good for:

Unknown landscapes without prior information
Problems with many local optima
Establishing a baseline for comparison
Cases where you need guaranteed coverage

Not ideal for:

Very expensive objective functions (use SMBO instead)
Fine-tuning when you have a good starting point
Very high-dimensional spaces

Algorithm Comparison

Algorithm	Deterministic?	Coverage	Best Use Case
Random Search	No	Probabilistic	Baseline, high dimensions
Grid Search	Yes	Complete	Small, discrete spaces
Random Restart	No	Hybrid	Multi-modal with local structure
Random Annealing	No	Adaptive	Broad to focused search
Pattern Search	Yes	Structured	Derivative-free optimization
Powell’s Method	Yes	Dimensional	Separable functions
Lipschitz	Yes	Bounded	Functions with known smoothness
DIRECT	Yes	Hierarchical	Guaranteed convergence

Conceptual Comparison

How each global search algorithm covers a 2D search space. Random Search samples uniformly, Grid Search covers systematically, Pattern Search uses geometric patterns, and DIRECT divides hierarchically.

Visualization

Random Search on Sphere function — Random Search explores the space uniformly without bias.

Grid Search on Sphere function — Grid Search systematically covers the space.

Pattern Search on Sphere function — Pattern Search uses structured geometric patterns.

DIRECT on Sphere function — DIRECT divides space hierarchically, focusing on promising regions.

Algorithms