I'm trying to generate start points for my optimization problem in Matlab. At this point Im not worried about feasibility but only a fast way to generate the points from which I could test the performance of different algorithms available within fmincon. Though am not worried about feasibility I don't want to use random number generator and would prefer to use a more "systematic" approach as below.
As a simple example, assume I have 2 decision variables x1 and x2 and I can provide the min/max ranges for each of these 2 variables.
Like,
xlow=[2,9];% 2 represents the min possible value of decision variable x1 and 9 represent the minimum possible value of x2;
xhigh=[5,16];% 5 represents the max possible value of decision variable x1 and so on;
One start point that I can use is
Random_Point1=(x1ow+xhigh)/2;% centre of the rectangle formed by max/min of decision variables;
After running the optimization algorithm with above start point, let's assume I want to generate more start points. Now I can generate 4 additional start points based on the mid-point Random_Point1 and the 4 original vertices (another way to think about this is by dividing the original rectangle in to 4 equal size smaller rectangles and finding the centre of each of the rectangle)
Random_Point21 = (Random_Point1 + [xlow(1),xlow(2)])/2;
Random_Point22 = (Random_Point1 + [xlow(1),xhigh(2)])/2;
Random_Point23 = (Random_Point1 + [xhigh(1),xlow(2))/2;
Random_Point24 = (Random_Point1 + [xhigh(1),xhigh(2)])/2;
Now I again run the fmincon with above 4 start points.
After looking at the results, I decide to generate more start points. This time I can generate 16 start points by using the previously generated above start points. The way to think about this is dividing the original rectangle in to 16 equal pieces along the respective axis and finding the centre of each of the 16 rectangles
I would continue the process of generating start points and running fmincon till my solution is deemed satisfactory (I have some criteria on when I want to stop optimization process)
My question is, what approach should I use to generate these start points in the most efficient manner (quick). Whatever I wrote (similar to above hard-coding) is definitely not the right approach. I guess I need to use recursion
Stating the problem in general terms:-
a) Assume I have k decision variables and for each decision variable I have the min/max ranges
b) I want to start with generating the mid-point (easy) and then in first iteration generate 2^k points, in 2nd iteration generate 2^(2k) points, in 3rd iteration generate 2^(3K) points and so on.
Note, in my application the number of decision variable is not expected to be large (may be 3 or maximum 4)..the complexity I have is more in functional form of objective rather than # of decision variables. I'm stating this so that there are no worries about generating unpractical number of start points (like I will apply a condition that if in the pth iteration if 2^((p-1)k) was greater than 10K abort the generation process.
Note: I do have a working model albeit of another approach where for let's say 2 decision variables with given min/max I want 400 start points. I divide each of the individual decision variables to Square root of 400 and for all the resulting combinations I will have 400 points. I would prefer to use alternate approach and one of them is described above.
ndgrid
will work well for you, as long as you're happy running all of the optimisation steps in a batch. I assumed that the iterative subdivision was important to you (because maybe the optimisation step takes too long). $\endgroup$ – Dylan Richard Muir Aug 14 '14 at 9:24