[New Book] Click to get The Beginner's Guide to Data Science!
Use the offer code 20offearlybird to get 20% off. Hurry, sale ends soon!

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.

Kick-start your project with my new book Optimization for Machine Learning, including step-by-step tutorials and the Python source code files for all examples.

Let’s get started.

Local Optimization Versus Global Optimization

Local Optimization Versus Global Optimization
Photo by Marco Verch, some rights reserved.

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.

Want to Get Started With Optimization Algorithms?

Take my free 7-day email crash course now (with sample code).

Click to sign-up and also get a free PDF Ebook version of the course.

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

Articles

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.

Get a Handle on Modern Optimization Algorithms!

Optimization for Maching Learning

Develop Your Understanding of Optimization

...with just a few lines of python code

Discover how in my new Ebook:
Optimization for Machine Learning

It provides self-study tutorials with full working code on:
Gradient Descent, Genetic Algorithms, Hill Climbing, Curve Fitting, RMSProp, Adam, and much more...

Bring Modern Optimization Algorithms to
Your Machine Learning Projects


See What's Inside

8 Responses to Local Optimization Versus Global Optimization

  1. Avatar
    Francisco Cristancho January 29, 2021 at 11:08 am #

    Good afternoon doctor Brownlee,

    I would like to see a practical example on how to apply PSO or other global optimization algorithms for training. I’ve seen in some cases that it would lead to better results than GD based algorithms. Do you have some references about how to build a neural network with such a system?. Thanks for your time, i really appreciate your wonderful work

  2. Avatar
    Salman Zaidi March 10, 2021 at 10:37 am #

    Thanks for the article. It is certainly debatable to term the evolutionary or swarm algorithms as global search algorithm, when they cannot provide with a precise probabilistic statement about finding the global optima with certain probability/confidence. I like to call them local stochastic search with relatively higher probability not to get stuck at the local optima (thanks to the exploratory characteristics, such as mutation) as compared to the local deterministic search algorithm.

  3. Avatar
    Anwar Zaman April 15, 2021 at 9:00 pm #

    Suppose you have applied the optimization method to a certain problem and is trapped into local minima? You are required to achieve the global optimum point. What steps are required to be taken to achieve the best optimum solution?

    plz answr if any one.

    • Avatar
      Jason Brownlee April 16, 2021 at 5:30 am #

      Each project will have a specific goal, perhaps you need the best optima, perhaps you need a good enough optima given the time you have.

      Typically we cannot locate the best optima in the given time/resources. It’s too challenging.

  4. Avatar
    Patrick May 6, 2022 at 1:47 am #

    Which ML models can find parameters that find global optima of the objective function?

    Please I will be glad if you help answer this question

Leave a Reply