# AnalyticBridge

A Data Science Central Community

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

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

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

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

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)?
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

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.

 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:
 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. Experiment 3 Experiment 4: Conclusion The approach seems promising and works well in different contexts:  I'm quite sure that many improvements can be implemented. I'm looking forward to receive your comments, ideas and other comparative tests. Stay tuned!  cristian

Views: 655

Comment