[Octave-patch-tracker] [patch #8918] fgridsearch as a gridsearch alternative to fminsearch

[Kai Torben Ohlhus]

Follow-up Comment #4, patch #8918 (project octave):

Please don't feel discouraged, but I really want to understand, what makes
your function better than existing tools.

Looking at your examples, I don't like them, as they only reveal things I
don't understand about your algorithm or need more documentation:

Example I - is in my opinion as elegant as writing the code of comment #1, and
the results are only as good as choosing the grid.


>> fh = @(x) x(1)^2 + x(2)^2;
>> [params, fval] = fgridsearch(fh , [-1, 0, 1], [-1, 0, 1])
params =

   0   0

fval = 0
>> [params, fval] = fgridsearch(fh , [-1, 0.4, 1], [-1, 0.4, 1])
params =

   0.40000   0.40000

fval =  0.32000



Example II - has four equal minima on each edge of the grid! Here the code of
comment #1 would even perform "better". This behavior of finding only one (and
which one?) minimum must be clearly documented to be reliable.


>> [X, Y] = ndgrid ([-1, 0, 1], [-1, 0, 1]);
>> X = X(:);
>> Y = Y(:);
>> Z = -(X.^2 + Y.^2);
>> fmin = min (Z)
fmin = -2
>> [X(find (Z == min (Z))), Y(find (Z == min (Z)))]
ans =

  -1  -1
   1  -1
  -1   1
   1   1


Example III - My understanding of the example is a minimum near [-100 -100]
with fval=-10. Maybe document this, it is tedious to find out.


>> [X, Y] = meshgrid (linspace(-200, 200, 100));
>> Z = -10*exp(-((X-100).^2 + (Y-100).^2)) - 3*exp(-(X.^2 + Y.^2));
>> mesh (X,Y,Z)


Moreover I think this example just shows the feature of function handles and
totally misleads, what fgridsearch should do.

fgridsearch does not (as I thought) search in this example for a minimum on
the grid using fminsearch to help this. The returned params lies on the grid


>> fh = @(x) -10*exp(-(sumsq(x - [-100 -100]))) - 3*exp(-sumsq(x));
>> gh = @(x) nthargout(2, @fminsearch, fh, x);
>> range = linspace(-200, 200, 10)
range =

 Columns 1 through 8:

  -200.000  -155.556  -111.111   -66.667   -22.222    22.222    66.667  
111.111

 Columns 9 and 10:

   155.556   200.000
>> [params, fval] = fgridsearch(gh, range, range)

params =

  -155.56  -155.56

fval = -9.9999


but the function value for params is not the minimum!


>> fh(params)

ans = -0
>> [x, fval] = fminsearch (fh, params)

x =

  -100.00  -100.00

fval = -9.9999


It is just a point from the grid, that converged to the smallest local minimum
MAYBE on the grid, as fminsearch embedded in @gh does not care about the given
grid. In the following input, the starting point lies on the grid, but
converges outside, and this is what fgridsearch would return without any
warning for this example!


>> [x, fval] = fminsearch (fh, [range(end) range(end)])
x =

   234.51   328.78

fval = -0
>> [params, fval] = fgridsearch(gh, [200 201], [200 201])
params =

   200   200

fval = -0



I think for global optimization the overloaded fminsearch for intervals
http://octave.sourceforge.net/interval/function/@infsup/fminsearch.html
does a "better" job. I respects the boundaries and delivers rigorous
inclusions. Using the interval package, I get:


>> pkg install -forge interval
>> pkg load interval
>> fh = @(x) -10*exp(-(sumsq(x - [-100 -100]))) - 3*exp(-sumsq(x))
>> [x, fval] = fminsearch (fh, infsup ("[-200, 200] [-200, 200]"))
x ⊂ 1×2 interval vector

   [-200, -10.693]   [-200, -0.57177]

fval ⊂ [-10.001, -10]


Here I am sure to find the global minimum within these bounds. I added the
package maintainer, maybe he can give a hint on how to improve Example III
with his interval package.


    _______________________________________________________

Reply to this item at:

  <http://savannah.gnu.org/patch/?8918>

_______________________________________________
  Message sent via/by Savannah
  http://savannah.gnu.org/