Speeding up exhaustive search

I need to find the global minimum of a function using exhaustive search. I have 10 function variables x1,x2,x3,...,x10 ∈ [0,10]. In order to produce all possible combinations of those function variables, i have written a code with 10 for loops and check their value.

Although this works, i would like to speed it up because it takes too much time to finish. Parfor can not help me here because the loops are not independent.

I would like some suggestions on how to speed up this code. Part of my code:

x=zeros(1,10); 
for x1=1:10
  x(1)=x(1)+step; %step=1 so at each iteration x(1)=1,2,3,...,10
  for x2=1:10
      if x(2)==10
          x(2)=0;
      end
      x(2)=x(2)+step;

   end
repeat for each variable
%evaluate f(x1,x2,x3,...,x10)

end

[Cedric]

Could you post, at least partially, your code?

[Cedric]

For that you should look at what the Optimization toolbox has to propose, because your are not exhaustive here (note that even the best methods won't be exhaustive); what happens if your global minimum lies in between two steps which are both characterized by a value of f greater than other values of f elsewhere?

The Optim. toolbox will provide you with tools using variable steps, that will be better suited for what you are trying to achieve.

[Doug Hull]

Are X1, X2, etc constrained to be integers? It is not clear.

[dimitris]

Firstly, thank you for replying.

About the subject, the idea is to reduce gradually the step, but first i must speed up my code, because for step=1 it takes too much time, imagine what will happen for step=0.1 or less. I have already used genetic algorithm from optimization toolbox but now i want to do this exhaustively.

Answer 1

[Alan Weiss]

If I understand you correctly, you have 11 possible values for each component, so are planning to execute 11^10 evaluations. That is an awful lot of computing.

Is it possible to vectorize your code? If so, you could evaluate, say, 11^5 points at once, return the values, and take the minimum. I mean, write your objective function as a function of a single vector x = (x(1),...,x(10), and evaluate it for all values of x(6),...,x(10) simultaneously. You would have to perform this evaluation only about 11^5 times, once for each possible value of x(1),...,x(5). For an example of what I mean, see this example of evaluating a vectorized function.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

Answer 2

[Doug Hull]

This is going to be so dependent on your problem.

Is it smooth? Can you start with a 3x3x3x... grid, then search in the most likely areas?

Have you run the profiler? This will tell you where the code is running the slowest.

You will have to show us the algorithm for any realistic help on this. Just modify the question (rather than comment) with the new information.