A conceptual overview of gradient free optimization algorithms, part one of two.
This video is part of an introductory optimization series.
TRANSCRIPT:
Hello, and welcome to Introduction To Optimization. This video covers gradient free algorithms.
Gradient based algorithms and gradient free algorithms are the two main types of methods for solving optimization problems. In this video, we will survey a variety of gradient free algorithms and discuss some of the basic ideas behind how they work.
The main difference between gradient based and gradient free algorithms is that gradient free algorithms do not require derivatives. This means that they can be used for optimization problems where derivatives can’t be obtained, or are difficult to obtain. This can include functions that are discrete, discontinuous, or noisy. This makes gradient free algorithms very flexible in the types of problems they can be applied to. The major disadvantage of gradient free algorithms is that they are generally much slower than gradient based algorithms.
There are a huge variety of gradient free algorithms, and many variations on those algorithms. Let’s take a look at some of the most common:
Exhaustive Search
First off, Exhaustive Search.
The simplest, and most inefficient gradient free optimization method is to try every possible solution and pick the best answer. While this approach may work for very small problems, with larger problems it quickly becomes impossible.
Genetic Algorithms
Genetic algorithms are another type of gradient free optimization algorithm. Genetic algorithms are based on the ideas of biology and evolution. Instead of proposing just a single solution to an optimization problem, a genetic algorithm generates many possible solutions that form a “population”. For example, if we were trying to optimize x and y, a population would be formed from various combinations of values of x and y. The solutions are scored using a fitness function, or objective function to decide which solutions are better than others. These candidate solutions are then recombined so that the best solutions “reproduce” to form a new generation of solutions with the best traits of the previous solutions. This continues until improvement stops or the maximum number of generations is reached. Let’s observe the progress of a genetic algorithm on the function x^3 + 15x^2 + y^3 +15y^2.
Particle Swarm
Particle swarm is similar to a genetic algorithm in that it creates a population, or in this case a swarm of possible solutions at each iteration. Each solution, or particle in the swarm has a direction and velocity. At each iteration, the movement of the particle is determined by a mixture of the direction it is currently moving, the direction of the best point it has found in the past, and the direction of the best point the whole swarm has discovered. The idea is that more and more particles will eventually move towards areas where better solutions are found, and that the swarm will eventually converge to the optimal value.