In
applied mathematics
Applied mathematics is the application of mathematical methods by different fields such as physics, engineering, medicine, biology, finance, business, computer science, and industry. Thus, applied mathematics is a combination of mathemati ...
and
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a local optimum of an
optimization problem
In mathematics, computer science and economics, an optimization problem is the problem of finding the ''best'' solution from all feasible solutions.
Optimization problems can be divided into two categories, depending on whether the variables ...
is a solution that is optimal (either
maximal or minimal) within a
neighboring set of candidate solutions. This is in contrast to a
global optimum, which is the optimal solution among
all possible solutions, not just those in a particular neighborhood of values.
Continuous domain
When the function to be optimized is
continuous
Continuity or continuous may refer to:
Mathematics
* Continuity (mathematics), the opposing concept to discreteness; common examples include
** Continuous probability distribution or random variable in probability and statistics
** Continuous g ...
, it may be possible to employ
calculus
Calculus, originally called infinitesimal calculus or "the calculus of infinitesimals", is the mathematics, mathematical study of continuous change, in the same way that geometry is the study of shape, and algebra is the study of generalizati ...
to find local optima. If the
first derivative exists everywhere, it can be equated to zero; if the function has an
unbounded domain
Domain may refer to:
Mathematics
*Domain of a function, the set of input values for which the (total) function is defined
** Domain of definition of a partial function
** Natural domain of a partial function
**Domain of holomorphy of a function
* ...
, for a point to be a local optimum it is
necessary that it satisfy this equation. Then the
second derivative test provides a
sufficient
In logic and mathematics, necessity and sufficiency are terms used to describe a conditional or implicational relationship between two statements. For example, in the conditional statement: "If then ", is necessary for , because the truth of ...
condition for the point to be a local maximum or local minimum.
Search techniques
Local search or
hill climbing
numerical analysis, 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 solutio ...
methods for solving 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
basins of attraction, each consisting of
all initial points which have a given local optimum as the final point of the local search trajectory.
A local optimum can be isolated (surrounded by non-locally-optimal points) or
part of a
plateau
In geology and physical geography, a plateau (; ; ), also called a high plain or a tableland, is an area of a highland consisting of flat terrain that is raised sharply above the surrounding area on at least one side. Often one or more sides ...
, a locally optimal region with more than one point of equal value.
If the problem to be solved has all locally optimal points with the same value of the function to be
optimized, local search effectively solves the global problem: finding a local optimum delivers
a 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 function.
In many cases, local optima deliver sub-optimal solutions to the global problem, and
a local search method needs to be modified to continue the search
beyond local optimality; see for example
iterated local search,
tabu search Tabu search is a metaheuristic search method employing local search methods used for mathematical optimization. It was created by Fred W. Glover in 1986
and formalized in 1989.
Local (neighborhood) searches take a potential solution to a pro ...
, reactive search optimization, and
simulated annealing.
See also
{{Commons category, Local optimum
*
Maxima and minima
In mathematical analysis, the maxima and minima (the respective plurals of maximum and minimum) of a function, known collectively as extrema (the plural of extremum), are the largest and smallest value of the function, either within a given r ...
Mathematical optimization