bugGNU Octave - Bugs: bug #55263, fminsearch not converging well

 
 

bug #55263: fminsearch not converging well

Submitter:  Giovanni Ciriani <gciriani>
Submitted:  Fri 21 Dec 2018 06:59:29 PM UTC
   
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  None
Status:  Works For Me Assigned to:  None
Originator Name:  Open/Closed:  * Closed
Release:  * 4.4.1 Operating System:  * Any
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Sat 22 Dec 2018 03:43:04 PM UTC, comment #5: 

As Rik suggest: you can compare your examples with the original algorithm by Nick Higham and report potential differences.

The original MATLAB implementation "nmsmax.m" is available from:

http://www.maths.manchester.ac.uk/~higham/mctoolbox/

Kai Torben Ohlhus <siko1056>
Group Member
Sat 22 Dec 2018 03:40:13 PM UTC, comment #4: 

"This algorithm is better-suited to functions which have discontinuities" refers to the alternative, a gradient-based search such as fminunc which works best on continuous functions that, ideally, also have continuous first and second derivatives.

Unfortunately, "better-suited" does not imply that it will work on all functions with discontinuities.  The original academic paper and code implementation are from N.J. Higham.  It is possible that the implementation in Octave is incorrect, but the comments in the code suggest that the implementation was taken directly from Higham with modifications done only for Octave syntax.  As another reference point, Matlab's implementation of the algorithm performs even worse.

Hence, I don't think it is the translation of the algorithm to code that is the problem, but the actual algorithm itself.  There may be tunable parameters, such as the size of the contract and expand steps, which would make a difference.  You might run some experiments on tweaking that portion of the algorithm.  If you were successful, there would also need to be an accompanying theoretical justification before changing the existing parameters.

Depending on your inclination, this sort of improvement to a base optimization algorithm could form the basis of an academic paper.

Rik <rik5>
Group administrator
Sat 22 Dec 2018 12:25:35 PM UTC, comment #3: 

I further tested the case with 2D data and 1D data with discontinuities. In the 1D case the Nelder-Mead method performs very well, regardless of discontinuities. This supports the point of view that the 2D and higher implementation has some incorrect indexing somewhere, where it is decided along which dimension to perform the contracting and the shrinking portion of the algorithm.

Giovanni Ciriani <gciriani>
Sat 22 Dec 2018 03:13:01 AM UTC, comment #2: 

Perhaps what you are saying is correct, but I think we need to have stronger arguments to dispose of this behavior. If one looks at line 29-30 of the code it states: "This algorithm is better-suited to functions which have discontinuities". So that would seem to clear your objection that my function has discontinuities. The more I look at the data during the iteration, the more the behavior seems to go against the Nelder Mead strategy. When the discontinuity is being reached, the simplex should advance in the dimension that is further away from the discontinuity, but it does not.

Thank you for suggesting that loading the optim package is not needed.

Giovanni Ciriani <gciriani>
Fri 21 Dec 2018 08:22:57 PM UTC, comment #1: 

I think you are expecting more from the algorithm than is reasonably possible.  There appears to be a discontinuity in the function at the coordinates of the maximum.


octave:6> fun ([9 9 9])
ans = -244
octave:7> fun ([9 9 9+10*eps])
ans = -0


This is going to make life very hard for the algorithm, even a derivative-free one.  For fun, I tried your example in Matlab and the output is far worse, x = [2.18, 9.0, 9.0], objf = -169.9.

You can play around with the starting point, the TolFun and TolX options in optimset, to see if you can get the algorithm to do what you want, but I couldn't.

I uploaded a second version of the example file that removes code that is specific to your system, such as C:\octave.  And fminsearch is part of core octave so there is no need no load the optim pkg.


(file #45713)

Rik <rik5>
Group administrator
Fri 21 Dec 2018 06:59:29 PM UTC, original submission:  

fminsearch seems to not converge up to where it should. It's possible there is an implementation error of the algorithm with a higher number of dimensions. I have attached an example where it should converge to point 9,9,9 to give the minimum value of the objective function at -244, and instead it stops at 9,9,8.7 for a value -240.48. The function is straightforward linear so it should have no problem arriving closer to the edge at 9,9,9 by minimizing the size of the simplex. Instead the algorithm reports that the size of the simplex is down to  2.1916e-10 and the step of the function is 7.5600e-08.

The attached file runs the whole example.

Giovanni Ciriani <gciriani>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #45713:  badNelderMead2.m added by rik5 (1KiB - text/x-matlab)
file #45712:  badNelderMead.m added by gciriani (1KiB - text/plain)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by siko1056 (Posted a comment)
  • -email is unavailable- added by rik5 (Updated the item)
  • -email is unavailable- added by gciriani (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 group members can vote.

     

    Follow 5 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2019-01-24 mtmiller Open/ClosedOpen Closed
    2018-12-21 rik5 Attached File- Added badNelderMead2.m, #45713
        StatusNone Works For Me
        Operating SystemMicrosoft Windows Any
    2018-12-21 gciriani Attached File- Added badNelderMead.m, #45712

    Back to the top

    Powered by Savane 3.13-4448.
    Corresponding source code