MATLAB: Patternsearch polls out of mesh points

Question

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

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