Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Local optimum
Summary
In applied mathematics and computer science, a local optimum of an optimization problem 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. Importantly, a global optimum is necessarily a local optimum, but a local optimum is not necessarily a global optimum.
When the function to be optimized is continuous, it may be possible to employ calculus to find local optima. If the first derivative exists everywhere, it can be equated to zero; if the function has an unbounded domain, for a point to be a local optimum it is necessary that it satisfy this equation. Then the second derivative test provides a sufficient condition for the point to be a local maximum or local minimum.
Local search or hill climbing 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, 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.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.