strange behavior of fminsearch

Hi,

I'm solving a simple optimization problem using fminsearch and fminsearch is behaving in a strange way, and I don't know why.

After a few hundred iterations and function evaluations, the value of the objective function will stop decreasing, but the optimization routine continues, either because TolX or TolFun are smaller than the change of the relevant variables. However, "what I see" of the objective function (displayed in "min f(x)" and using the "@optimplotfval" option) is clearly not changing. So, I would use the "stop" bottom of the Optimization PlotFcns figure, recover the parameters that were obtained in the last iteration, and restart the optimization from those parameters and... right in the first one or two iterations, the fminsearch is making the value of the objective function decrease again. Why is this happening?

So, to be very clear, this is what I see

[alphahat]=fminsearch(@(x) objfun(x,mk,tol),alpha,Options)

   Iteration   Func-count     min f(x)         Procedure
     599          898          58.9532         reflect
     600          899          58.9532         reflect
     601          900          58.9532         reflect
     602          909           58.953         shrink
     603          910           58.953         reflect
  .
  .
  .
    2198         4949           58.953         reflect
    2199         4950           58.953         reflect
    2200         4959           58.953         shrink
    2201         4960           58.953         reflect
    2202         4961           58.953         reflect
    2203         4970           58.953         shrink
    2204         4979           58.953         shrink
  Optimization terminated prematurely by user.

alphahat =

       0.066037
       0.079153
      0.0055039
          10.95
       -0.15036
       -0.54456
       -0.64515

>> alpha=alphahat;
>> [alphahat]=fminsearch(@(x) objfun(x,mk,tol),alpha,Options)

   Iteration   Func-count     min f(x)         Procedure
       0            1          58.9534         
       1            8          58.9534         initial simplex
       2           10          58.9534         contract inside
       3           12          58.6142         expand
       4           14          58.1076         expand
       5           15          58.1076         reflect
       6           16          58.1076         reflect
       7           18          57.5256         expand
       8           19          57.5256         reflect
       9           21          56.9234         expand
      10           22          56.9234         reflect
      11           23          56.9234         reflect
      12           25          56.4965         expand
      13           27          55.6554         expand
      14           28          55.6554         reflect
      15           30          54.5408         expand
      16           31          54.5408         reflect
      17           32          54.5408         reflect
      18           33          54.5408         reflect
      19           34          54.5408         reflect
      20           36          53.3618         expand
      21           37          53.3618         reflect
      22           38          53.3618         reflect
      23           39          53.3618         reflect
      24           40          53.3618         reflect
      25           41          53.3618         reflect
      26           42          53.3618         reflect
      27           43          53.3618         reflect
      28           45          53.3618         contract outside

Any ideas? Thanks.

Answer 1

[Matt J]

The reason you are not seeing a change in the objective function value is because it is only displayed for you to 4 decimal places. But the value continues to change in the unshown decimal places.

It also looks like the initial set of iterations are reaching a saddle point or local min. When you restart the optimization, a new simplex is constructed and the descent proceeds based on that. The new simplex samples a larger neighborhood of the saddle point than the initial set of iterations was doing and is therefore able to find a more productive path of descent, dislodging the algorithm from the saddle point.

[Fernando]

I don't think that's the case here because starting from the same initial values, regardless of where I restart the optimization after iteration 605, I see a big "jump" that is not seen if I just allow the original optimization to continue. Note that after "retarting" changes happen at the first decimal level.

[Fernando]

I'm sorry, it seems we were writing at the the same time. Is there any way to create a new simplex within the original optimization without having to restart the optimization?

[Matt J]

See my edited response. Your reboot of the optimization changes the simplex that the Nelder-Mead algorithm uses to sample the neighborhood of the current point. This appears to dislodge it from a local stationary point.

I would also remark that your problem is pushing the number of unknowns that Nelder-Mead will typically handle gracefully. The Nelder-Mead algorithm is only theoretically guaranteed to converge for 1 unknown, and its empirical convergence performance starts to deteriorate as you go beyond 6 or so.

[Matt J]

Is there any way to create a new simplex within the original optimization without having to restart the optimization?

I don't think that's the right way to approach the difficulty you're having. When you have local solutions where the algorithm can get trapped, the best you can do is try to avoid them by choosing a better initial guess. If you have many, many local solutions that are hard to avoid, it may be time to question whether you have a pathological objective function.

[Fernando]

Thanks