Local search algorithms are widely applied to numerous hard computational problems, including problems from computer science (particularly artificial intelligence), mathematics, operations research, engineering, and bioinformatics.
This requires a neighborhood relation to be defined on the search space.
This local-optima problem can be cured by using restarts (repeated local search with different initial conditions), randomization, or more complex schemes based on iterations, like iterated local search, on memory, like reactive search optimization, on memory-less stochastic modifications, like simulated annealing.
Local search does not provide a guarantee that any given solution is optimal.
The search can terminate after a given time bound or when the best solution found thus far has not improved in a given number of steps.