Generating start point in a systematic manner for fmincon

Hi,

(I posted this in stack exchange 2 days back but didn't get a response. Hope it works here).

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 and yet systematic 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.

One approach that I have been using successfully (which I guess is a very common approach) is, if I have 2 decision variables with given min/max range for each of the 2 decision variables and let's suppose I want 400 start points. I divide each of the individual decision variables min/max range to Square root of 400 thereby giving 20 points in one decision variable and 20 in another decision variable and for all the possible combinations I will have 400 points. I'm considering alternate approaches to generating start points and one of them is described 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 each of the 4 smaller rectangles in previous iteration in to 4 pieces each so that we have 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 (coding) 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)

c) In second iteration, first take the mid-point from b) and divide the original space in to 2^k sub-spaces (parallel to each axis) and find the centre of these thereby generating 2^k points

d) In 3rd iteration, repeat c) thereby generating 2^(2k) points

e) In 4th iteration, repeat d) 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 10000 abort the generation process.

Answer 1

[Matt J]

      k=2;
      range={[0,1],[3,4]}; %[min,max] ranges for each of k unknowns
      maxIter=3;

       for i=1:maxIter

           sampling=(2^-i:2^(1-i):1);

        for j=1:k

          samps{j}=diff(range{j})*sampling+range{j}(1);

        end

        clear X0;
        [X0{1:k}]=ndgrid(samps{:});
         X0=reshape( cat(k+1,X0{:}), [],k),  %Sets of initial points

       end

[Hari]

Thanks again Matt. I tried this quickly and it works great. Impressed with how concise the code is.

PS: I'm yet to fully understand the logic used so will post back later in case of any clarifications.