Global Optimization
Seek the best solution over an entire landscape of many local minima, where gradient methods alone are not enough.
The challenge
Local methods like gradient descent find the nearest valley, but nonconvex objectives can have many local minima, and the global optimum may be far from any starting point. Global optimization aims to find, or provably bound, the best solution over the whole feasible region. In general this is NP-hard, so methods trade guarantees for practicality.
Two broad families
- Deterministic methods (branch-and-bound, interval analysis, Lipschitz optimization) partition the space and prune regions that provably cannot contain the optimum, giving rigorous bounds.
- Stochastic and heuristic methods (simulated annealing, evolutionary algorithms, particle swarm, Bayesian optimization) explore probabilistically and usually lack guarantees but scale to hard, black-box problems.
Exploration versus exploitation
Every global method balances exploration (searching new regions to avoid missing the global optimum) against exploitation (refining promising regions to converge). Too much exploration wastes evaluations; too much exploitation gets trapped in a local optimum. The balance is the central design choice of any global optimizer.
Branch and bound
Deterministic branch-and-bound recursively splits the domain and computes lower and upper bounds on the objective in each subregion. Subregions whose lower bound exceeds the best known solution are discarded. With valid bounds this converges to the certified global optimum, though the tree can grow exponentially.
Black-box and expensive objectives
When the objective is a costly simulation with no gradient, surrogate-based and Bayesian methods build a cheap model to decide where to sample next, minimizing the number of expensive evaluations. This is the regime of most engineering design optimization, where each evaluation may run a full physics solver.
Global search methods explore high-dimensional design spaces to find configurations that local methods, anchored to a starting guess, would miss.