A local optimization algorithm, also called a local search algorithm, is an algorithm intended to locate a local optima. It is suited to traversing a given region of the search space and getting close to (or finding exactly) the extrema of the function in that region.
… local optimization methods are widely used in applications where there is value in finding a good point, if not the very best.
Local search algorithms typically operate on a single candidate solution and involve iteratively making small changes to the candidate solution and evaluating the change to see if it leads to an improvement and is taken as the new candidate solution.
A local optimization algorithm will locate the global optimum:
If the local optima is the global optima, or
If the region being searched contains the global optima.
These define the ideal use cases for using a local search algorithm.
There may be debate over what exactly constitutes a local search algorithm; nevertheless, three examples of local search algorithms using our definitions include:
Now that we are familiar with local optimization, let’s take a look at global optimization.
A global optimum is the extrema (minimum or maximum) of the objective function for the entire input search space.
Global optimization, where the algorithm searches for the global optimum by employing mechanisms to search larger parts of the search space.
An objective function may have one or more than one global optima, and if more than one, it is referred to as a multimodal optimization problem and each optimum will have a different input and the same objective function evaluation.
Global Optimization: Locate the optima for an objective function that may contain local optima.
An objective function always has a global optima (otherwise we would not be interested in optimizing it), although it may also have local optima that have an objective function evaluation that is not as good as the global optima.
The global optima may be the same as the local optima, in which case it would be more appropriate to refer to the optimization problem as a local optimization, instead of global optimization.
The presence of the local optima is a major component of what defines the difficulty of a global optimization problem as it may be relatively easy to locate a local optima and relatively difficult to locate the global optima.
A global optimization algorithm, also called a global search algorithm, is intended to locate a global optima. It is suited to traversing the entire input search space and getting close to (or finding exactly) the extrema of the function.
Global optimization is used for problems with a small number of variables, where computing time is not critical, and the value of finding the true global solution is very high.
Global search algorithms may involve managing a single or a population of candidate solutions from which new candidate solutions are iteratively generated and evaluated to see if they result in an improvement and taken as the new working state.
There may be debate over what exactly constitutes a global search algorithm; nevertheless, three examples of global search algorithms using our definitions include:
Particle Swarm Optimization
Now that we are familiar with global and local optimization, let’s compare and contrast the two.
Local vs. Global Optimization
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.
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.
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.