Local optimum
Encyclopedia
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
.
Applied mathematics
Applied mathematics is a branch of mathematics that concerns itself with mathematical methods that are typically used in science, engineering, business, and industry. Thus, "applied mathematics" is a mathematical science with specialized knowledge...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
.
A local optimum of a combinatorial optimization
Combinatorial optimization
In applied mathematics and theoretical computer science, combinatorial optimization is a topic that consists of finding an optimal object from a finite set of objects. In many such problems, exhaustive search is not feasible...
problem is a solution that is optimal (either maximal or minimal
Maxima and minima
In mathematics, the maximum and minimum of a function, known collectively as extrema , are the largest and smallest value that the function takes at a point either within a given neighborhood or on the function domain in its entirety .More generally, the...
) within a neighboring set of solutions. This is in contrast to a global optimum
Global optimum
In mathematics, a global optimum is a selection from a given domain which yields either the highest value or lowest value , when a specific function is applied. For example, for the function...
, which is the optimal solution among all possible solutions.
Local search
Local search (optimization)
In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
or hill climbing
Hill climbing
In computer science, hill climbing is a mathematical optimization technique which belongs to the family of local search. It is an iterative algorithm that starts with an arbitrary solution to a problem, then attempts to find a better solution by incrementally changing a single element of the solution...
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
Plateau
In geology and earth science, a plateau , also called a high plain or tableland, is an area of highland, usually consisting of relatively flat terrain. A highly eroded plateau is called a dissected 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
Local search (optimization)
In computer science, local search is a metaheuristic method for solving computationally hard optimization problems. Local search can be used on problems that can be formulated as finding a solution maximizing a criterion among a number of candidate solutions...
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
Iterated local search
Iterated local search is a term in applied mathematics and computer sciencedefining a modification of local search or hill climbing methods for solving discrete optimization problems.Local search methods build a trajectory in configuration...
, tabu search
Tabu search
Tabu search is a mathematical optimization method, belonging to the class of trajectory based techniques. Tabu search enhances the performance of a local search method by using memory structures that describe the visited solutions: once a potential solution has been determined, it is marked as...
, reactive search optimization
Reactive search optimization
Reactive search optimization defines local-search heuristics based on machine learning, a family of optimization algorithms based on the local search techniques...
,
simulated annealing
Simulated annealing
Simulated annealing is a generic probabilistic metaheuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. It is often used when the search space is discrete...
.