1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I have a uploaded a function to the Matlab File Exchange that does the majority of what you want, I think. The function explores a parameter space by subdividing the space across borders formed by arbitrary decision variables, so to find a high-resolution characterisation of the borders: [Characterise borders in a parameter space][1] The final sampling of the space will not be uniform, but will depend on the behaviour of your system within the parameter space. [1]: mathworks.com/matlabcentral/fileexchange/… $\endgroup$ – Dylan Richard Muir Aug 11 '14 at 10:30
  • $\begingroup$ Thanks @Dylan, I will take a look at the file and get back in case of questions (at first glance it looks like a in-depth and sophisticated implementation). Btw, I had posted this same question to matlabCentral and got a workable solution using ndgrid. $\endgroup$ – Hari Aug 13 '14 at 15:59
  • $\begingroup$ 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
  • $\begingroup$ I'm running the optimization in a "pesudo-iterative" manner. I use the pause feature within the loop and whenever required -depending on the quality of results in command window - pause it. $\endgroup$ – Hari Aug 16 '14 at 14:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.