Local and global search optimization algorithms solve different problems or answer different questions.
A local optimization algorithm should be used when you know that you are in the region of the global optima or that your objective function contains a single optima, e.g. unimodal.
A global optimization algorithm should be used when you know very little about the structure of the objective function response surface, or when you know that the function contains local optima.
Local optimization, where the algorithm may get stuck in a local optimum without finding a global optimum.
— Page 37, Computational Intelligence: An Introduction, 2007.
Applying a local search algorithm to a problem that requires a global search algorithm will deliver poor results as the local search will get caught (deceived) by local optima.
- Local search: When you are in the region of the global optima.
- Global search: When you know that there are local optima.
Local search algorithms often give computational complexity grantees related to locating the global optima, as long as the assumptions made by the algorithm hold.
Global search algorithms often give very few if any grantees about locating the global optima. As such, global search is often used on problems that are sufficiently difficult that “good” or “good enough” solutions are preferred over no solutions at all. This might mean relatively good local optima instead of the true global optima if locating the global optima is intractable.
It is often appropriate to re-run or re-start the algorithm multiple times and record the optima found by each run to give some confidence that relatively good solutions have been located.
- Local search: For narrow problems where the global solution is required.
- Global search: For broad problems where the global optima might be intractable.
We often know very little about the response surface for an objective function, e.g. whether a local or global search algorithm is most appropriate. Therefore, it may be desirable to establish a baseline in performance with a local search algorithm and then explore a global search algorithm to see if it can perform better. If it cannot, it may suggest that the problem is indeed unimodal or appropriate for a local search algorithm.
- Best Practice: Establish a baseline with a local search then explore a global search on objective functions where little is known.
Local optimization is a simpler problem to solve than global optimization. As such, the vast majority of the research on mathematical optimization has been focused on local search techniques.
A large fraction of the research on general nonlinear programming has focused on methods for local optimization, which as a consequence are well developed.
— Page 9, Convex Optimization, 2004.
Global search algorithms are often coarse in their navigation of the search space.
Many population methods perform well in global search, being able to avoid local minima and finding the best regions of the design space. Unfortunately, these methods do not perform as well in local search in comparison to descent methods.
— Page 162, Algorithms for Optimization, 2019.
As such, they may locate the basin for a good local optima or the global optima, but may not be able to locate the best solution within the basin.
Local and global optimization techniques can be combined to form hybrid training algorithms.
— Page 37, Computational Intelligence: An Introduction, 2007.
Therefore, it is a good practice to apply a local search to the optima candidate solutions found by a global search algorithm.