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:
“Reporters for tabloid newspapers beat a path to the park entrance each summer when the national convention of nudists is held, but the cult’s requirement that visitors disrobe is an obstacle to complete coverage of nudist news. Local residents interested in the nudist movement but as yet unwilling to affiliate make observations from rowboats in Great Egg Harbor River.”
—For the State of New Jersey, 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)