Patternsearch polls out of mesh points

I've encountered an issue with the patternsearch algorithm. I have a global optimization problem with an objective function that involves a CDF (as in a probability model). In order to try and restrict the search pattern to within regions which are relatively non-flat, I imposed a maximum mesh size of 1024, since large parameter values are essentially the same in terms of the optimization problem I'm interested in.

This is correctly passed in via the patternsearch optimization options (all other options are default):

 options = 
            MaxIter: Inf
        MaxFunEvals: Inf
          TimeLimit: 25000
        MaxMeshSize: 1024
            Display: 'iter'
              Cache: 'on'

I use an initial starting point which is seeded based on a subset of the data, and is a vector with magnitude no greater than 54. After running patternsearch, the solution vector it returns is impossibly large: on the order of 10^26.

Based on the algorithm, this should be impossible. You can see the sequence of polls below:

 Iter     f-count          f(x)      MeshSize     Method
    0        1         313483             1      
    1       13         312984             2     Successful Poll
    2       35         312783             4     Successful Poll
    3       57         312540             8     Successful Poll
    4       81         312348            16     Successful Poll
    5      113         311814            32     Successful Poll
    6      151         311780            64     Successful Poll
    7      189         311772           128     Successful Poll
    8      247         267213           256     Successful Poll
    9      285         267200           512     Successful Poll
   10      323         267197          1024     Successful Poll
   11      362         267193          1024     Successful Poll
   12      428         266744          1024     Successful Poll
   13      467         266733          1024     Successful Poll
   14      543         266733           512     Refine Mesh
   ...
   51     2751         258424            64     Refine Mesh
   52     2828         258424            32     Refine Mesh
   53     2867         258421            64     Successful Poll

At this point, the run times out and returns the best point to date: a vector with an element on the order to 10^26.

Based on my understanding of patternsearch, the maximal element could be polled would be on the order of 53,000. This implies that patternsearch is somehow polling elements far outside the maximal mesh, which is highly undesirable.

Does anyone have any insight as to why this is occurring? If so, can you suggest any way to address this? I would still like to use this algorithm, because it has desirable properties and is computationally reasonable.

This looks a bit like a bug, like some kind of overflow error, but it's hard to determine why it's happening. If it matters, the optimization function calls a parfor loop using several workers.

Answer 1

[Alan Weiss]

The behavior is, in fact, due to the ScaleMesh option being 'on'. I did not realize before how large the ScaleMesh option allowed the step to be as a function of the current size and the current mesh. It turns out that the step can be as large as the mesh size times the current x size, so your x point can grow exponentially even after the mesh size is capped.

To fix, just set the ScaleMesh option to 'off'.

My colleagues and I will be looking into possibly changing this behavior, or at least documenting it more clearly.

Thanks for your very clear report, and again I apologize for taking so long to give you a definitive answer.

Alan Weiss

MATLAB mathematical toolbox documentation

[jgg]

Hi Alan

Thanks for the solution; I've made this change and it looks like it has helped. Appreciate it.

Answer 2

[Alan Weiss]

I am not sure why this is happening. I wonder if you can perform a bit more analysis on the points patternsearch visits, perhaps using a plot function or an output function. I am interested in knowing the evolution of the infinity norm (maximum absolute value) of the current point vector as the iterations progress. You can use the built-in @psplotbestx plot function, and maybe @psplotmeshsize.

You should know that patternsearch by default scales the mesh, a behavior that is controlled by the ScaleMesh option. But I doubt that this would give rise to the behavior you report.

Also, could you please report the exact options call and patternsearch call that you made? Something like

options = psoptimset('MaxIter','Inf',...)
[x,fval] = patternsearch(fun,x0,[],[],[],[],lb,ub,nonlcon,options)

Alan Weiss

MATLAB mathematical toolbox documentation

[jgg]

Hi Alan

I'm going to run the optimization as you suggested; this could take a while since it's a very large problem (we're running this on a cluster using the Matlab compiler, which might be relevant (?)) but this offers no display, so I'm going to set it up to run locally. I'll let you know what it it finds.

The problem is actually already scaled and centered (every variable has an impact on the objective of about 1), so I agree that the mesh scaling should not matter here.

The exact options are:

 options = psoptimset('Cache', 'on', 'Display', 'iter','MaxFunEvals',Inf, 'MaxIter',Inf, 'TimeLimit', timelimit, 'MaxMeshSize', 2^10)
 [out,fval,exitflag,output] = patternsearch(func,spoint,[],[],[],[],lb,ub,[],options);
 %where we have the following called earlier
 lb = -Inf.*ones(1,K); %K = 39
 ub = Inf.*ones(1,K);
 lb(2*k+1) = 0; %2*k+1 is K-3 in this problem
 timelimit = 25,000 %for instance

I will post an update when I have some plots. Hopefully I can duplicate the behaviour locally.

[jgg]

Hi Alan

As you suggested, I ran the optimization with the plot functions called. You can see the variation below. This is iteration 10 and 11 of the routine. I cancelled it after this point, since it appears to have already demonstrated the behaviour.

The discontinuity in the best point appears to happen when it hits the maximum mesh size. Then, for whatever reason, it polls points far outside the maximal meshgrid (you can see the mesh size plot is always under control).

The results are slightly different, mainly due to some changes I've made (that are difficult to reverse) but the behaviour appears to be fairly robust.

Let me know if you have any suggestions or thoughts.

 Iter     f-count          f(x)      MeshSize     Method
    0        1         313490             1      
    1       13         313013             2     Successful Poll
    2       35         312767             4     Successful Poll
    3       57         312517             8     Successful Poll
    4       81         312380            16     Successful Poll
    5      105         312351            32     Successful Poll
    6      137         312135            64     Successful Poll
    7      175         312123           128     Successful Poll
    8      213         312116           256     Successful Poll
    9      252         312090           512     Successful Poll
   10      314         311802          1024     Successful Poll
   11      352         311774          1024     Successful Poll
   12      391         311769          1024     Successful Poll

Iteration 11

Iteration 10

[Alan Weiss]

Thanks for the info. Our development staff is largely on break right now. I hope to have some answers for you in a week or so.

Alan Weiss

MATLAB mathematical toolbox documentation

[jgg]

Thanks Alan.

Let me know what you find!

[jgg]

Hi Alan

Just wondering if there was an answer or suggestion for this from your team?

[Alan Weiss]

The team is still not all back from winter break. I expect an answer in a few days. Sorry for not keeping you informed.

Alan Weiss

MATLAB mathematical toolbox documentation