AnalyticBridge

A Data Science Central Community

Subscribe to DSC Newsletter

Function minimization: Simulated Annealing led by variance criteria vs Nelder Mead

Most of the datamining problems can be reduced as a minimization/maximization problem.

... click here to read the entire post

Examples

Let's consider easy scenarios where the function cost is conditionated just by two parameters.

... click here to read the entire post

As you can see the above problems have in common a massive presence of local minimum :).

Let's see how to handle these problems through an approach that I define hybrid, that is, obtained mixing different methods and properties.

Simulated Annealing (SA) "variance based" approach

... click here to read the entire post

Variance trick

Let's consider a sampling in two different region of a function f :

sampling_1 in a region having a smooth minimum and evaluate such points
sampling_2 in a region having a spiky minimum and evaluate such points

Take now the variance of these evaluated sets.
How does the variance of f(sampling_1) change respect the variance of f(sampling_2)?
Here you are the answer:

As you can see the variance can be used as indicator of a minimum region of the cost function.

Instead of explore randomly the solution space, the approach I propose is led by the variance used as above.

What happens if the smooth valley is a global minimum?

There are two intuitive factors to avoid that the algorithm jams in a local minimum:

1. The acceptance law admit also pejorative solutions.

2. The sampling procedure moderate by variance (if the variance is chosen high enough) allows explorations of better regions.

The algorithm

... click here to read the entire post

Tests
Let's see how the approach works.
As usual, all my experiments are compared with other techniques. In this case I chose as comparative method the well known "Nelder Mead" method.
I tried to optimize the Nelder Mead method playing around its param setting: shrink ratio, contraction ratio and reflection ratio.

... click here to read the entire post

On the left side it has been represented the solution found by Nelder Mead method.
On the right side the solution found by the SA presented in this post: the blue point depicts the starting point and the red point depicts the solution found.
The last chart shows the space solution explored

... click here to read the entire post

EXPERIMENT 2: