Local optimum is a term in applied mathematics and computer science.
A local optimum of a combinatorial optimization problem is a solution that is optimal (either maximal or minimal) within a neighboring set of solutions. This is in contrast to a global optimum, which is the optimal solution among all possible solutions.
Local search or hill climbing methods for solving discrete optimization problems start from an initial configuration and repeatedly move to an improving neighboring configuration. A trajectory in search space is generated, which maps an initial point to a local optimum, where local search is stuck (no improving neighbors are available). The search space is therefore subdivided into attraction basins, consisting of all initial points which have a given local optimum as final point of the local search trajectory. A local optimum can be isolated (surrounded by non locally-optimal point) or part of a plateau, a locally optimal region with more than one point.
If the problem to be solved has all local optimal points with the same value of the function to be optimized, local search effectively solves the problem: finding a local optimum delivers the globally optimal solution.
The locality of the optimum is dependent on the neighborhood structure as defined by the local search method that is used for optimizing the solution.
In many cases, local optima deliver sub-optimal solutions, and a local search method needs to be modified to continue the search beyond local optimality, see for example iterated local search, tabu search, reactive search optimization, simulated annealing.
Famous quotes containing the words local and/or optimum:
“Eclecticism is the degree zero of contemporary general culture: one listens to reggae, watches a western, eats McDonald’s food for lunch and local cuisine for dinner, wears Paris perfume in Tokyo and “retro” clothes in Hong Kong; knowledge is a matter for TV games. It is easy to find a public for eclectic works.”
—Jean François Lyotard (b. 1924)
“Everywhere—all over Africa and South America ... you see these suburbs springing up. They represent the optimum of what people want. There’s a certain sort of logic leading towards these immaculate suburbs. And they’re terrifying, because they are the death of the soul.... This is the prison this planet is being turned into.”
—J.G. (James Graham)