Naive Parallel Minimization
Multiple simultaneous minimizations applied to the Rastrigin function
Introduction
Previous work has shown that the Rastrigin function is difficult for the dlib library’s find_min_global function to solve. When searching in a volume with edge length of 20, finding the global minimum in even 3 dimensions is not computationally feasible.
In this analysis, we consider the performance of a naive parallel algorithm which finds a global minimum by running a local minimum algorithm from different starting points. The local minimum algorithm is based on the BFGS search strategy.
The parallel algorithm uses multiple TBB tasks, each started on a random starting point within the search region. Each task finds a local minimum. It then records that minimum in a shared set of solutions. It then queries the shared set of solutions to determine whether the global minimum has yet been found. If the global minimum has not been found, the task finishes by scheduling another task that starts a new search from a random location. If the global minimum has been found, no new work is scheduled.
The program finishes when all the tasks finish (and thus soon after a task find the global minimum).
In our “testing” version of the algorithm, the shared store of all search results is of unbounded size. This allows us, at the end of the work, to analyze all the candidate solutions that were found.
Analysis
The algorithm is of non-deterministic behavior for two reasons:
- it uses pseudorandom number generation to generate the “random” starting points, and
- the order of execution of threads, and thus tasks, is not deterministic.
This naive algorithm can solve the problem that the dlib::find_min_global algorithm could not solve very quickly.
2 dimensions
The two-dimensional problem seems very easy for the algorithm. One run resulted in the execution of 153 local minimizations. The wall-clock execution time was bout 0.68 seconds.
In two dimensions we can visualize the minimizations by plotting the starting point and ending point for each local minimization. In the plot below, the red points are the starting points and the black points are the ending points for each minimization.
In this space, there are 441 distinct minima, of which 1 is the global minimum. Few of these minima were found, and very few found more than once. Short “distances” between starting and stopping points are most common, but some long paths do happen. The distribution of distances is shown in the figure below.
The relationship between the distance traveled and the time taken for the minimization can be seen in a scatter plot:
Is seems there is only a small tendency for minimizations that “travel further” to take a longer time to complete.
5 dimensions
One run in 5 dimensions resulted in the execution of 108436 local minimizations. The successful start was number 108425 (in order of finishing). The wall-clock execution time (run on my laptop) was about 0.85 seconds.
The running time of the local minimization that yielded the global minimum was 0.0247 milliseconds. The distribution of running times for all local minimizations is shown below. Note the log \(x\) scale.
There is a clear trend to have a high-side tail. There seems to be a weak correlation between the distance between the starting and ending point of the local minimization and the time it takes. This can be seen in the following scatter plot (note the log scales on both \(x\) and \(y\) axes).
6 dimensions
One run in 6 dimensions resulted in the execution of 9649770 local minimizations. The successful start was number 9649759 (in order of finishing). The wall-clock execution time (run on my laptop) was about 74 seconds.
The running time of the local minimization that yielded the global minimum was 0.0181 milliseconds. The distribution of running times for all local minimizations is shown below. Note the log \(x\) scale.
There is a clear trend to have a high-side tail. There seems to be a weak correlation between the distance between the starting and ending point of the local minimization and the time it takes. This can be seen in the following scatter plot (note the log scales on both \(x\) and \(y\) axes).
7 dimensions
One run in 7 dimensions resulted in 173227244 local minimizations. The successful start was number 173227233. The wall-clock execution time was about 1834 seconds.
There is no indication that any individual minimization task takes very long. It is merely the number of tasks needed to blunder into the right minimum that seems to make the running time so large. Note that a significant part of the reason the long runs are long is that all of the local solutions are kept.
8 dimensions
With the code altered to keep only the top 10 solutions, it is possible to run a problemk in 8 dimensions. The times to completion, as a function of the number of dimensions, are:
| dimensionality | wall-clock time (s) |
|---|---|
| 8 | 223.870 |
| 7 | 64.242 |
| 6 | 28.180 |
| 5 | 0.293 |
| 4 | 0.084 |
| 3 | 0.023 |
| 2 | 0.023 |
| 1 | 0.020 |
