Random-restart optimization

Random-restart optimization repeatedly runs a local optimization algorithm from independently sampled starting points and retains the best result. It exploits multiple basins of attraction without requiring the local solver itself to escape a local extremum.

If each restart has probability $p$ of entering a desired basin, independent restarts miss it with probability $(1-p{)}^N$ after $N$ attempts. This formula quantifies the benefit only for the specified starting distribution and basin; neither $p>0$ nor a finite run certifies a global extremum. Recording the starting distribution and stopping rule makes computational comparisons reproducible.