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:
“The improved American highway system ... isolated the American-in-transit. On his speedway ... he had no contact with the towns which he by-passed. If he stopped for food or gas, he was served no local fare or local fuel, but had one of Howard Johnson’s nationally branded ice cream flavors, and so many gallons of Exxon. This vast ocean of superhighways was nearly as free of culture as the sea traversed by the Mayflower Pilgrims.”
—Daniel J. Boorstin (b. 1914)
“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)