Gradient-free optimization

The most straightforward, and most inefficient gradient free optimisation method is to try every possible solution and pick the best answer. While this approach may work for very small problems, it quickly becomes impossible to apply with an increasing problem size.

The Nelder-Mead downhill simplex algorithm

The Nelder-Mead downhill simplex algorithm is a commonly used gradient-free algorithm. In n dimensions, it uses a shape with n+1 edges (the so-called simplex) to search for an optimal solution. The simplex shape flip flops towards its goal, growing, shrinking, and changing its shape according to a set of rules listed below.

This algorithm uses only function values and is robust but relatively slow. It will work reasonably well for non-differentiable functions. It can be used within the optim() function by using the method “Nelder-Mead”.

Simulated annealing

Annealing is a process in which metal or glass is heated, and then allowed to slowly cool at a controlled rate. It changes the properties of a metal, making it more ductile and workable. Simulated annealing uses the idea of slowly cooling metal in an optimisation algorithm. An initial random point is taken, which is followed by random movements to other positions. The new positions are evaluated to see if they are better than the previous ones. Initially, some bad solutions are accepted to allow the algorithm to explore, perhaps finding its way out of a local minimum. As time goes on, the “temperature” is reduced, and fewer bad solutions are accepted. Eventually, only solutions that are better than the previous ones are accepted. The process works like a ball bouncing on a rough surface, where it is initially bouncing very hard but slowly loses its momentum and starts only rolling down along the gradient. Eventually it will come to a stop, hopefully at the minimum point. Simulated annealing belongs to the class of stochastic global optimisation methods. It uses only function values but is relatively slow. It is not a general-purpose method but can be very useful in getting to a good value on a very rough surface. The optim() method “SANN” is by default a variant of simulated annealing given in Belisle (1992). With the additional argument temp, we can control the “temperature” of the simulation.