patchGNU Octave - Patches: patch #8918, fgridsearch as a gridsearch...

 
 

patch #8918: fgridsearch as a gridsearch alternative to fminsearch

Submitter:  Max Görner <maxg>
Submitted:  Fri 26 Feb 2016 09:49:36 AM UTC
   
 
Category:  Core : new function Priority:  5 - Normal
Status:  Wont Do Privacy:  Public
Assigned to:  None Open/Closed:  Closed
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Mon 07 Dec 2020 02:10:34 AM UTC, comment #6: 

No improvements for 4 years.  Closing.

Kai Torben Ohlhus <siko1056>
Group Member
Thu 07 Jul 2016 05:31:52 AM UTC, comment #5: 

Hi Kai,

I am not sure what you want to improve in Example III. The interval fminsearch function's focus is to find fval. If you are interested in the corresponding x values, you can find them with the interval fsolve function. Use optimset parameters on either function to improve accuracy.


... (Example III) ...
>> x = fsolve (fh, infsup ("[-200, 200] [-200, 200]"), fval)
x ⊂ 1×2 interval vector

   [-100.4, -99.609]   [-100.79, -99.218]


I must agree that the function is not very useful as a generic tool, because it doesn't do much more than "min (f (meshgrid (...)))" would do. I would consider to use it in special cases where I know that my grid is good and not too big.

There is no bisection or heuristics of any kind, so all we have is a "brute force" attempt to traverse the grid.

Oliver

Anonymous
Wed 01 Jun 2016 01:09:08 PM UTC, comment #4: 

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.

Kai Torben Ohlhus <siko1056>
Group Member
Tue 31 May 2016 09:57:19 AM UTC, comment #3: 

I improved the documentation a tiny bit. Most importantly, I added another example which demonstrates more clearly why I consider fgridsearch to be beneficial. I'll copy the example here for convenience:


%Here fgridsearch is used to explore several starting points for a
%fminsearch optimisation. That way the global minimum is found.
fh = @(x) -10*exp(-(sumsq(x - [-100 -100]))) - 3*exp(-sumsq(x));
gh = @(x) nthargout(2, @fminsearch, fh, x);
range = linspace(-200, 200, 10);
[params, fval] = fgridsearch(gh, range, range);


I have to admit that this function only helps to hide loops, though.

If the new example makes the function interesting, I'll happily work on the other points.

(file #37315)

Max Görner <maxg>
Mon 14 Mar 2016 08:38:18 PM UTC, comment #2: 

I want to address only the question about the need of this function now.

You're right when you note that the function in the example can be written as in your small listing. However, that's not the whole story. You can pass in any function taking any number of inputs and you'll get back the best value found by a gridsearch. Think of a complex model for which some meta parameters need to be found. This saves plenty of loops and can make more readable.

If this is considered interesting, I'll try to fix the other issues.

Max Görner <maxg>
Tue 08 Mar 2016 12:46:13 PM UTC, comment #1: 

This function basically does something according to the following code:


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


Some points to consider:

1. This function is not MATLAB compatible. Is there a particular reason/scientific discipline, that needs this function and is not able to write code, like the small listing above?
2. The documentation is not very detailed, better document the input and output. See other Octave functions as guideline:

http://hg.savannah.gnu.org/hgweb/octave/file/74a676d5ce09/scripts/optimization/fminsearch.m

3. Does this function work for dimensions > 2?
4. How does this function perform for large scale problems?
5. I notice function crashes, without help for the user, for nonconforming input like


params = fgridsearch(@(x) x(1)^2 + x(2)^2, [-1, 0, 1], [-1, 0, 1], 'a')
params = fgridsearch(@(x) x(1)^2 + x(2)^2, [-1, 0, 1], [-1, 0, 1], {1})


To sum up, I don't see the benefits of this function. If one needs to evaluate the whole optimization domain, like fgridsearch does, one will code something like in this post above. fminsearch addresses another use case, where only the optimum matters and from this point one can try to evaluate a local grid, to save lots of computational effort.

Kai Torben Ohlhus <siko1056>
Group Member
Fri 26 Feb 2016 09:49:36 AM UTC, original submission:  

I wrote a small function performing a gridsearch on a function handle.

The benefit is mainly that one saves multiple nested loops, so code using this function gains readability. Furthermore, in an utopian future that function might be parallelised better than nested loops.

Another benefit is that one can get back all function evaluations, so an detailed analysis of the results can be done. This is not possible with fminsearch at the moment.

I would be glad for any criticism of that function. Furthermore I think that it would be a good alternative to have either in Octave itself or in the optim package.

Max Görner <maxg>

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attach Files:
   
   
Comment:
   

Attached Files
file #37315:  fgridsearch.m added by maxg (3KiB - text/x-objective-c)
file #36470:  fgridsearch.m added by maxg (2KiB - d2l/unknowntype)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by lachlan (Updated the item)
  • -email is unavailable- added by siko1056
  • -email is unavailable- added by siko1056 (Posted a comment)
  • -email is unavailable- added by maxg (Submitted the item)
  •  

    There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

    Only logged-in users can vote.

     

    Follow 6 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2020-12-07 siko1056 StatusNone Wont Do
        Open/ClosedOpen Closed
    2016-07-07 lachlan CategoryNone Core : new function
    2016-06-01 siko1056 Carbon-Copy- Added oheim
    2016-05-31 maxg Attached File- Added fgridsearch.m, #37315
    2016-02-26 maxg Attached File- Added fgridsearch.m, #36470

    Back to the top

    Powered by Savane 3.13-f8d8.
    Corresponding source code