

Hello everyone,
I am trying to write a grid search algorithm for optimization. It would evaluate an objective function over all the possible points on the grid, and return the minimum value and its location.
I was able to do this easily for a 4dimensional function. This needed four nested for loops. This solution however, its not elegantly scalable to a 20dimensional function.
For example, let's say the search domain over any search direction is 10 to 10, with some grid resolution. To do it for a 4dimensional function, I used:
for i = 1:N
for j = 1:N
for k = 1:N
for l = 1:N
xPoint = [x(i) x(j) x(k) x(l)]';
fEval_x = colville(xPoint);
if fEval_x < fmin
fmin = fEval_x;
xmin = xPoint;
endif
endfor
endfor
endfor
endfor
Where colville() is an optimization toy function.
Does anyone have a suggestion on how to avoid 20 nested for loops when trying to scale this algorithm up to higher dimensions?
Thanks a bunch,
Brad Ridder


On Thu, May 19, 2011 at 1:43 PM, clustro <[hidden email]> wrote:
Hello everyone,
I am trying to write a grid search algorithm for optimization. It would
evaluate an objective function over all the possible points on the grid, and
return the minimum value and its location.
I was able to do this easily for a 4dimensional function. This needed four
nested for loops. This solution however, its not elegantly scalable to a
20dimensional function.
For example, let's say the search domain over any search direction is 10 to
10, with some grid resolution. To do it for a 4dimensional function, I
used:
for i = 1:N
for j = 1:N
for k = 1:N
for l = 1:N
xPoint = [x(i) x(j) x(k) x(l)]';
fEval_x = colville(xPoint);
if fEval_x < fmin
fmin = fEval_x;
xmin = xPoint;
endif
endfor
endfor
endfor
endfor
Where colville() is an optimization toy function.
Does anyone have a suggestion on how to avoid 20 nested for loops when
trying to scale this algorithm up to higher dimensions?
Thanks a bunch,
Brad Ridder

V
Why do every point? Is the the function smooth of hilly in each dimension? Are there lots of local minimums?
das
_______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave


I am not particularly interested in using grid search for practical purposes; the purpose is to compare grid search with better methods (e.g. simulated annealing, genetic algorithm, etc.).
The point is to compare the performance of simulated annealing with grid search in terms of accuracy and run time. The toy functions I am using are indeed very hilly.
Thank you very much for your time,
Brad Ridder
On Thu, May 19, 2011 at 3:00 PM, Doug Stewart <[hidden email]> wrote:
On Thu, May 19, 2011 at 1:43 PM, clustro <[hidden email]> wrote:
Hello everyone,
I am trying to write a grid search algorithm for optimization. It would
evaluate an objective function over all the possible points on the grid, and
return the minimum value and its location.
I was able to do this easily for a 4dimensional function. This needed four
nested for loops. This solution however, its not elegantly scalable to a
20dimensional function.
For example, let's say the search domain over any search direction is 10 to
10, with some grid resolution. To do it for a 4dimensional function, I
used:
for i = 1:N
for j = 1:N
for k = 1:N
for l = 1:N
xPoint = [x(i) x(j) x(k) x(l)]';
fEval_x = colville(xPoint);
if fEval_x < fmin
fmin = fEval_x;
xmin = xPoint;
endif
endfor
endfor
endfor
endfor
Where colville() is an optimization toy function.
Does anyone have a suggestion on how to avoid 20 nested for loops when
trying to scale this algorithm up to higher dimensions?
Thanks a bunch,
Brad Ridder

V
Why do every point? Is the the function smooth of hilly in each dimension? Are there lots of local minimums?
das
 Bradley James Ridder Chakrabart Group Graduate Student School of Chemical Engineering Purdue University
_______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave


On 19 May 2011 12:43, clustro < [hidden email]> wrote:
> for i = 1:N
> for j = 1:N
> for k = 1:N
> for l = 1:N
> xPoint = [x(i) x(j) x(k) x(l)]';
> fEval_x = colville(xPoint);
> if fEval_x < fmin
> fmin = fEval_x;
> xmin = xPoint;
> endif
> endfor
> endfor
> endfor
> endfor
>
> Where colville() is an optimization toy function.
>
> Does anyone have a suggestion on how to avoid 20 nested for loops when
> trying to scale this algorithm up to higher dimensions?
I don't understand the full extent of your problem, you basically want
the minimum over the nfold tensor product of a vector?
You might be able to do this with arrayfun, although I don't
immediately see how to avoid the actual tensoring.
 Jordi G. H.
_______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave


On Thu, May 19, 2011 at 1:43 PM, clustro <[hidden email]> wrote: Hello everyone,
I am trying to write a grid search algorithm for optimization. It would evaluate an objective function over all the possible points on the grid, and return the minimum value and its location.
I was able to do this easily for a 4dimensional function. This needed four nested for loops. This solution however, its not elegantly scalable to a 20dimensional function.
For example, let's say the search domain over any search direction is 10 to 10, with some grid resolution. To do it for a 4dimensional function, I used:
for i = 1:N for j = 1:N for k = 1:N for l = 1:N xPoint = [x(i) x(j) x(k) x(l)]'; fEval_x = colville(xPoint); if fEval_x < fmin fmin = fEval_x; xmin = xPoint; endif endfor endfor endfor endfor
Where colville() is an optimization toy function.
Does anyone have a suggestion on how to avoid 20 nested for loops when trying to scale this algorithm up to higher dimensions?
Thanks a bunch,
Brad Ridder
 V Is the the function smooth of hilly in each dimension? Are there lots of local minimums? I sometimes run into this sort of thing. There is no pregeneration of the grid that provides any sort of indication of the values in the grin. Often it gets populated by discontinuous results. Mike G. _______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave

Administrator

In reply to this post by Jordi Gutiérrez Hermoso2
On May 19, 2011, at 4:05 PM, Jordi Gutiérrez Hermoso wrote:
> On 19 May 2011 12:43, clustro < [hidden email]> wrote:
>> for i = 1:N
>> for j = 1:N
>> for k = 1:N
>> for l = 1:N
>> xPoint = [x(i) x(j) x(k) x(l)]';
>> fEval_x = colville(xPoint);
>> if fEval_x < fmin
>> fmin = fEval_x;
>> xmin = xPoint;
>> endif
>> endfor
>> endfor
>> endfor
>> endfor
>>
>> Where colville() is an optimization toy function.
>>
>> Does anyone have a suggestion on how to avoid 20 nested for loops when
>> trying to scale this algorithm up to higher dimensions?
>
> I don't understand the full extent of your problem, you basically want
> the minimum over the nfold tensor product of a vector?
>
> You might be able to do this with arrayfun, although I don't
> immediately see how to avoid the actual tensoring.
>
>  Jordi G. H.
I'm not sure how to use arrayfun(), but using cellfun() ...
N = 4;
Nf = factorial (N);
input_permutations = mat2cell (perms (4), ones (Nf, 1), 4);
opt_fun = @(x) colville (x{:});
fEval_x = cellfun (opt_fun, input_permutations);
x_min = input_permutations (fEval_x == min (fEval_x));
The resulting x_min will be a cell array whose length is equal to the number of results equal to the minimum value.
Ben
p.s. I haven't tested this code, so there may be some typo.
_______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave


Hello,
Thank you all who responded.
Mr. Abbott,
Your code does not work as is, but I see what you were getting at, and it gave me an idea, and it worked. However, the Octave perms() command is not what is needed. There is however, a function on the MATLAB central file exchange called "combn()", which returns all combinations of a size k from a vector of size n >= k. This can be used to create all the needed combinations of vectors, without needing all those for loops for indexing.
The only downer is that making huge matrices of vector combinations leads to memory problems, which I am not sure how to remedy at this time.
Thank you all again,
Brad Ridder
2011/5/19 Ben Abbott <[hidden email]>
On May 19, 2011, at 4:05 PM, Jordi Gutiérrez Hermoso wrote:
> On 19 May 2011 12:43, clustro < [hidden email]> wrote:
>> for i = 1:N
>> for j = 1:N
>> for k = 1:N
>> for l = 1:N
>> xPoint = [x(i) x(j) x(k) x(l)]';
>> fEval_x = colville(xPoint);
>> if fEval_x < fmin
>> fmin = fEval_x;
>> xmin = xPoint;
>> endif
>> endfor
>> endfor
>> endfor
>> endfor
>>
>> Where colville() is an optimization toy function.
>>
>> Does anyone have a suggestion on how to avoid 20 nested for loops when
>> trying to scale this algorithm up to higher dimensions?
>
> I don't understand the full extent of your problem, you basically want
> the minimum over the nfold tensor product of a vector?
>
> You might be able to do this with arrayfun, although I don't
> immediately see how to avoid the actual tensoring.
>
>  Jordi G. H.
I'm not sure how to use arrayfun(), but using cellfun() ...
N = 4;
Nf = factorial (N);
input_permutations = mat2cell (perms (4), ones (Nf, 1), 4);
opt_fun = @(x) colville (x{:});
fEval_x = cellfun (opt_fun, input_permutations);
x_min = input_permutations (fEval_x == min (fEval_x));
The resulting x_min will be a cell array whose length is equal to the number of results equal to the minimum value.
Ben
p.s. I haven't tested this code, so there may be some typo.
 Bradley James Ridder Chakrabarti Group Graduate Student School of Chemical Engineering Purdue University
_______________________________________________
Helpoctave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/helpoctave

