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:
“Wags try to invent new stories to tell about the legislature, and end by telling the old one about the senator who explained his unaccustomed possession of a large roll of bills by saying that someone pushed it over the transom while he slept. The expression “It came over the transom,” to explain any unusual good fortune, is part of local folklore.”
—For the State of Montana, U.S. public relief program (1935-1943)
“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)