Nested Grids Directed Random Search Optimization

[Namir]

I wrote recently about the optimization of multi-variable functions using random searches. While this algorithm is easy to code, it requires a high number of iterations to produce refined guesses close to the true answers.

I have recently combined nested grid search and random searches to explore various parts the of "trusted region" (defined by ranges of search for each variable). This approach allows you to focus on feasible parts of your search region and use relatively fewer iterations. The algorithm works in general by:

1) Divide each search range by N, where N is usually a small integer (3, 4, 5, ans so on, but not much more). This division creates a grid with N^(number of variables) segments.
2) Randomly search in each grid segment using a relatively low number of iterations (100, to say 500). Keep track of the relative low/high sub-ranges that defines the segment with the best result.
3) Repeat steps 2 and 3 M times by taking the best segment as the new trust region.
4) Repeat steps 1 to 3 for say 30 to 50 times (and even less if calculations are really time consuming).
5) Calculate the mean, standard deviation, and confidence interval for each variable. The mean values should be close to the actual values.
6) Optional (do once). You can use the confidence intervals from step 5 as the new and better trust search region, and start again with step 1. When you reach step 5 you should get better results.

Yes I know. The above steps require A LOT of CPU time and power. I have been using this method to perform curve fitting for complex reversible chemical reactions by means of optimizing the sum of square differences between observed (or per-calculated, if you have no chemistry lab) and calculated concentration of the reaction's chemicals.

Namir