Local Optimization Versus Global Optimization

Optimization refers to finding the set of inputs to an objective function that results in the maximum or minimum output from the objective function.

It is common to describe optimization problems in terms of local vs. global optimization.

Similarly, it is also common to describe optimization algorithms or search algorithms in terms of local vs. global search.

In this tutorial, you will discover the practical differences between local and global optimization.

After completing this tutorial, you will know:

• Local optimization involves finding the optimal solution for a specific region of the search space, or the global optima for problems with no local optima.
• Global optimization involves finding the optimal solution on problems that contain local optima.
• How and when to use local and global search algorithms and how to use both methods in concert.

Let’s get started.

Tutorial Overview

This tutorial is divided into three parts; they are:

1. Local Optimization
2. Global Optimization
3. Local vs. Global Optimization

Local Optimization

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

Now that we are familiar with local optimization, let’s take a look at global optimization.

Global Optimization

A global optimum is the extrema (minimum or maximum) of the objective function for the entire input search space.

Global optimization, where the algorithm searches for the global optimum by employing mechanisms to search larger parts of the search space.

— Page 37, Computational Intelligence: An Introduction, 2007.

An objective function may have one or more than one global optima, and if more than one, it is referred to as a multimodal optimization problem and each optimum will have a different input and the same objective function evaluation.

• Global Optimization: Locate the optima for an objective function that may contain local optima.

An objective function always has a global optima (otherwise we would not be interested in optimizing it), although it may also have local optima that have an objective function evaluation that is not as good as the global optima.

The global optima may be the same as the local optima, in which case it would be more appropriate to refer to the optimization problem as a local optimization, instead of global optimization.

The presence of the local optima is a major component of what defines the difficulty of a global optimization problem as it may be relatively easy to locate a local optima and relatively difficult to locate the global optima.

Global optimization or global search refers to searching for the global optima.

A global optimization algorithm, also called a global search algorithm, is intended to locate a global optima. It is suited to traversing the entire input search space and getting close to (or finding exactly) the extrema of the function.

Global optimization is used for problems with a small number of variables, where computing time is not critical, and the value of finding the true global solution is very high.

— Page 9, Convex Optimization, 2004.

Global search algorithms may involve managing a single or a population of candidate solutions from which new candidate solutions are iteratively generated and evaluated to see if they result in an improvement and taken as the new working state.

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

• Genetic Algorithm
• Simulated Annealing
• Particle Swarm Optimization

Now that we are familiar with global and local optimization, let’s compare and contrast the two.

Local vs. Global Optimization

Local and global search optimization algorithms solve different problems or answer different questions.

A local optimization algorithm should be used when you know that you are in the region of the global optima or that your objective function contains a single optima, e.g. unimodal.

A global optimization algorithm should be used when you know very little about the structure of the objective function response surface, or when you know that the function contains local optima.

Local optimization, where the algorithm may get stuck in a local optimum without finding a global optimum.

— Page 37, Computational Intelligence: An Introduction, 2007.

Applying a local search algorithm to a problem that requires a global search algorithm will deliver poor results as the local search will get caught (deceived) by local optima.

• Local search: When you are in the region of the global optima.
• Global search: When you know that there are local optima.

Local search algorithms often give computational complexity grantees related to locating the global optima, as long as the assumptions made by the algorithm hold.

Global search algorithms often give very few if any grantees about locating the global optima. As such, global search is often used on problems that are sufficiently difficult that “good” or “good enough” solutions are preferred over no solutions at all. This might mean relatively good local optima instead of the true global optima if locating the global optima is intractable.

It is often appropriate to re-run or re-start the algorithm multiple times and record the optima found by each run to give some confidence that relatively good solutions have been located.

• Local search: For narrow problems where the global solution is required.
• Global search: For broad problems where the global optima might be intractable.

We often know very little about the response surface for an objective function, e.g. whether a local or global search algorithm is most appropriate. Therefore, it may be desirable to establish a baseline in performance with a local search algorithm and then explore a global search algorithm to see if it can perform better. If it cannot, it may suggest that the problem is indeed unimodal or appropriate for a local search algorithm.

• Best Practice: Establish a baseline with a local search then explore a global search on objective functions where little is known.

Local optimization is a simpler problem to solve than global optimization. As such, the vast majority of the research on mathematical optimization has been focused on local search techniques.

A large fraction of the research on general nonlinear programming has focused on methods for local optimization, which as a consequence are well developed.

— Page 9, Convex Optimization, 2004.

Global search algorithms are often coarse in their navigation of the search space.

Many population methods perform well in global search, being able to avoid local minima and finding the best regions of the design space. Unfortunately, these methods do not perform as well in local search in comparison to descent methods.

— Page 162, Algorithms for Optimization, 2019.

As such, they may locate the basin for a good local optima or the global optima, but may not be able to locate the best solution within the basin.

Local and global optimization techniques can be combined to form hybrid training algorithms.

— Page 37, Computational Intelligence: An Introduction, 2007.

Therefore, it is a good practice to apply a local search to the optima candidate solutions found by a global search algorithm.

• Best Practice: Apply a local search to the solutions found by a global search.

Further Reading

This section provides more resources on the topic if you are looking to go deeper.

Books

• Convex Optimization, 2004.
• Computational Intelligence: An Introduction, 2007.
• Algorithms for Optimization, 2019.

Articles

• Local search (optimization), Wikipedia.
• Global optimization, Wikipedia.

Summary

In this tutorial, you discovered the practical differences between local and global optimization.

Specifically, you learned:

• Local optimization involves finding the optimal solution for a specific region of the search space, or the global optima for problems with no local optima.
• Global optimization involves finding the optimal solution on problems that contain local optima.
• How and when to use local and global search algorithms and how to use both methods in concert.

Do you have any questions?
Ask your questions in the comments below and I will do my best to answer.

The post Local Optimization Versus Global Optimization appeared first on Machine Learning Mastery.