MATLAB: Pattern search seems to evaluate 4*N times the function in each iteration …

Global Optimization Toolboxoptimizationpatternsearch

Hello!
Pattern search should evaluate the function for 2*N times in each iteration, right? But it seems that it evaluates 4*N times in some iterations. I cannot figure out why. If you can provide an answer, it will be of great help to me because my function takes lots of time to evaluate. Thanks.
Here is how I set the options:
option=psoptimset('Display','Iter',...
                  'TolMesh',sqrt(1e-5),...
                  'Cache','on',...
                  'CacheTol',sqrt(1e-5),...
                  'CompletePoll','on',...
                  'PollMethod','MADSPositiveBasis2N',...
                  'OutPutFcns',@(a,b,c)Outfcn(a,b,c,'ps'));
Some outputs are below. My N=12. As you can see, whenever it goes from refine mesh to a successful poll, it evaluates the function for 48 times instead of 24… This means that for J iterations, it actually evaluates the function for more than 24*J times.
Iter     f-count          f(x)      MeshSize     Method
    0        1        18.0938             1      
    1       49        8.74728             1     Successful Poll
    2       97        5.93612             1     Successful Poll
    3      121        5.93612          0.25     Refine Mesh
    4      145        5.93612        0.0625     Refine Mesh
    5      193        3.73289          0.25     Successful Poll
    6      217        3.73289        0.0625     Refine Mesh
    7      265        3.62688          0.25     Successful Poll
    8      313        2.97285             1     Successful Poll
    9      337        2.97285          0.25     Refine Mesh
   10      361        2.97285        0.0625     Refine Mesh
   11      409          2.937          0.25     Successful Poll
   12      433          2.937        0.0625     Refine Mesh
   13      457          2.937       0.01562     Refine Mesh
   14      481          2.937      0.003906     Refine Mesh
   15      529        2.68362       0.01562     Successful Poll
   16      577        2.65236        0.0625     Successful Poll

Best Answer

I believe that the answer is that MADS has the behavior that when it finds a better point in a poll, it immediately tries polling again with the same mesh, so runs twice on every success. You set CompletePoll to 'on', so it runs 48 times on each success.
Why does it do this? Because MADS takes a new mesh on every iteration. But if a poll is successful, then the current mesh might be aligned well with a descent direction, so MADS tries again with the same mesh.
Just because it runs twice on each success does not mean that it is inherently a less efficient algorithm. It is not taking samples of the same points again, it is looking at new points, since it expands the mesh before sampling.
As this example shows, it can be inefficient to use a complete poll with MADS polling.
By the way, I am not sure that caching helps much with MADS polling, because the mesh changes each time. I suggest that, if you are going to use MADS, you try with caching off.
Alan Weiss
MATLAB mathematical toolbox documentation
Related Question