multistart

Multistart is a strategy used in optimization and search problems in which multiple starting points are employed to explore the solution space. The goal is to reduce the risk of getting trapped in poor local optima and to increase the chance of approaching a global optimum, especially for nonconvex or complex landscapes.

The typical workflow involves generating a set of starting points within the feasible region, running a local search or optimization method from each point (which may be gradient-based, derivative-free, or problem-specific), and then comparing the resulting solutions to select the best one. This process can be performed serially or in parallel, enabling more exhaustive exploration within the same time frame.

Starting points can be produced by random sampling, Latin hypercube sampling, regular grids, or problem-informed heuristics. Diversification strategies aim to spread starting points across the search space, sometimes with bias toward promising regions or near known good solutions to balance exploration and exploitation.

Multistart is applied across various domains, including nonlinear programming, continuous and discrete optimization, combinatorial optimization, and machine learning hyperparameter tuning. Advantages include improved robustness and higher likelihood of locating high-quality solutions, particularly in rugged landscapes. Disadvantages include increased computational cost and dependence on the number of starts and the quality of individual local solvers. Variants and related methods include multi-start hill climbing, multi-start simulated annealing, and multi-start evolutionary algorithms.