Local Optimization

Data Science, AI and ML
#1

A local optima is the extrema (minimum or maximum) of the objective function for a given region of the input space, e.g. a basin in a minimization problem.

… we seek a point that is only locally optimal, which means that it minimizes the objective function among feasible points that are near it …

— Page 9, Convex Optimization, 2004.

An objective function may have many local optima, or it may have a single local optima, in which case the local optima is also the global optima.

  • Local Optimization: Locate the optima for an objective function from a starting point believed to contain the optima (e.g. a basin).

Local optimization or local search refers to searching for the local optima.

A local optimization algorithm, also called a local search algorithm, is an algorithm intended to locate a local optima. It is suited to traversing a given region of the search space and getting close to (or finding exactly) the extrema of the function in that region.

… local optimization methods are widely used in applications where there is value in finding a good point, if not the very best.

— Page 9, Convex Optimization, 2004.

Local search algorithms typically operate on a single candidate solution and involve iteratively making small changes to the candidate solution and evaluating the change to see if it leads to an improvement and is taken as the new candidate solution.

A local optimization algorithm will locate the global optimum:

  • If the local optima is the global optima, or
  • If the region being searched contains the global optima.

These define the ideal use cases for using a local search algorithm.

There may be debate over what exactly constitutes a local search algorithm; nevertheless, three examples of local search algorithms using our definitions include:

  • Nelder-Mead Algorithm
  • BFGS Algorithm
  • Hill-Climbing Algorithm