Local optimum

Encyclopedia

**Local optimum**is a term in applied mathematics

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...

.