Wish to avoid multiple for loops, but don't know how to do it

classic Classic list List threaded Threaded
7 messages Options
Reply | Threaded
Open this post in threaded view
|

Wish to avoid multiple for loops, but don't know how to do it

clustro
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 4-dimensional function. This needed four nested for loops. This solution however, its not elegantly scalable to a 20-dimensional 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 4-dimensional 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
Reply | Threaded
Open this post in threaded view
|

Re: Wish to avoid multiple for loops, but don't know how to do it

Doug Stewart-4


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 4-dimensional function. This needed four
nested for loops. This solution however, its not elegantly scalable to a
20-dimensional 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 4-dimensional 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


_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Wish to avoid multiple for loops, but don't know how to do it

clustro
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 4-dimensional function. This needed four
nested for loops. This solution however, its not elegantly scalable to a
20-dimensional 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 4-dimensional 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



_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Wish to avoid multiple for loops, but don't know how to do it

Jordi Gutiérrez Hermoso-2
In reply to this post by clustro
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 n-fold 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.
_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

RE: Wish to avoid multiple for loops, but don't know how to do it

Mike G
In reply to this post by Doug Stewart-4

 

 

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 4-dimensional function. This needed four
nested for loops. This solution however, its not elegantly scalable to a
20-dimensional 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 4-dimensional 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

 

 I sometimes run into this sort of thing. There is no pre-generation of the grid that provides any sort of indication of the values in the grin. Often it gets populated by dis-continuous results.

Mike G.

 


_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Wish to avoid multiple for loops, but don't know how to do it

bpabbott
Administrator
In reply to this post by Jordi Gutiérrez Hermoso-2
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 n-fold 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.

_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave
Reply | Threaded
Open this post in threaded view
|

Re: Wish to avoid multiple for loops, but don't know how to do it

clustro
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 n-fold 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



_______________________________________________
Help-octave mailing list
[hidden email]
https://mailman.cae.wisc.edu/listinfo/help-octave