bugGNU Octave - Bugs: bug #35534, fminunc: FunValCheck buggy

 
 

bug #35534: fminunc: FunValCheck buggy

Submitter:  Olaf Till <i7tiol>
Submitted:  Wed 15 Feb 2012 01:44:00 PM UTC
   
 
Category:  None Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Other
Status:  Fixed Assigned to:  None
Originator Name:  Olaf Till Open/Closed:  * Closed
Release:  * dev Operating System:  * GNU/Linux
Fixed Release:  None Planned Release:  None
* Mandatory Fields

Add a New Comment Rich Markup
   

Jump to the original submission

Sat 18 Feb 2012 07:41:56 PM UTC, comment #6: 

The change was applied to the stable branch in this changeset (http://hg.savannah.gnu.org/hgweb/octave/rev/07c55bceca23).  The other extensions to include Inf testing and %!test blocks will go on the development branch.

Rik <rik5>
Group administrator
Fri 17 Feb 2012 11:32:14 AM UTC, comment #5: 

I didn't speak of reversing the search direction. Consider a search direction in which the function value first decreases and then increases until it gets too high (gets Inf). Algorithms sometimes test step-widths while not (much) changing search direction. If the first step width is too high it might produce an Inf value. The algorithm can then shorten the step width until it gets a function value less than current. The previous Inf value might be just due to the limits of floating point representation and not a programming error. A NaN value indicates a problem of a different kind.

But if you disagree, why don't you just make the change you propose? This problem is separate from my typo patch. The same applies for the tests.

As for the tests, my objection came from the fact that you explicitly named it a test for bug 35534 first, not a general test.

Olaf Till <i7tiol>
Group Member
Thu 16 Feb 2012 06:09:13 PM UTC, comment #4: 

Just because Matlab does something, doesn't mean it is wrong.  In this case, I don't see why we should avoid compatibility and keep Inf separate.

NaN and Inf are both saturating values in Octave which means any further mathematical operations involving them always return the same value. 

Inf - 1e6 == Inf
Nan + 2 == NaN

They represent dead-ends which the optimization algorithm may be unable to get out of.

Imagine that an optimization routine uses a first derivative to guess at the next value of the objective function.

Phi(n+1) = Phi(n) + d/dx (Phi).

As soon as Phi(n) hits Inf this sort of algorithm is locked.

This may not be a particular issue for fminunc but the FunValCheck option is supported across all the optimization routines and should have the same behavior across all of them as well.  Thus, if even one of the optimization routines does something similar to what I have described then Inf needs to be checked for.

Including Inf in the tests shouldn't be a problem for the actual algorithm in fminunc.  You assert that fminunc might detect the change from objective_value1 to Inf as a positive increase and therefore reverse the search direction.  If you are dealing with continuous functions, however, fminunc will have had ample warning that the objective function was increasing before hitting the value Inf.  It would have reversed the search course very early on, and if it didn't and actually reached Inf, then something is wrong with the search and FunValCheck should terminate the procedure.

If you are dealing with a crazy function with point discontinuities then I'm afraid there is always going to be trouble and you might need to restrict minimization to the continuous regions and do local minima searches in those regions.

As for testing, I want to be thorough and show not only that the feature works as expected, but also that it doesn't break anything else.  We know that it was a typo, but as a tester I need to treat the code as a black box.  The %!error statement shows that FunValCheck correctly detects a complex value.  The %!assert shows that there are no side effects in FunValCheck which would stop an ordinary function from working.


Rik <rik5>
Group administrator
Thu 16 Feb 2012 02:02:13 PM UTC, comment #3: 

Checking also for Inf may be Matlab compatible, but I'm not sure we should duplicate this behavior without good reason. A returned NaN can never be used by the algorithm, but an algorithm might correctly interpret a returned Inf as an increase of the value of the objective function. So checking for NaN or Inf seem to be differently motivated and should not necessarily be turned on by the same option.

And I would not see a need to include the "assert" line to check for the bug, since the bug was simply a random typo. Of course you can include the "error" line to check for FunValCheck catching complex values, but thats a different thing. I simply wanted to correct the typos.

Olaf

Olaf Till <i7tiol>
Group Member
Wed 15 Feb 2012 07:07:23 PM UTC, comment #2: 

The bug is confirmed, as well as your patch that fixes it.

Looking at the documentation for fminunc (http://www.mathworks.com/help/toolbox/optim/ug/fminunc.html) I see the following for the FunValCheck option.


Check whether objective function values are valid. 'on' displays an error when the objective function returns a value that is complex, Inf, or NaN. The default 'off' displays no error.


Could you expand your patch to also detect Inf values?  The isinf() function should be all that is required.

Also, could you add a %!test or %!assert block that exercises the new code?

Something like


%% Test for bug #35534
%!assert (fminunc (@(x) x^2, 1, optimset ("FunValCheck", "on"), 0, eps)
%!error <non-real value> fminunc (@(x) x + i, 1, optimset ("FunValCheck", "on"))



Rik <rik5>
Group administrator
Wed 15 Feb 2012 01:48:41 PM UTC, comment #1: 

The patch is attached.

(file #25067)

Olaf Till <i7tiol>
Group Member
Wed 15 Feb 2012 01:44:00 PM UTC, original submission:  

In current tip on the default branch (721a4a83cba6, 2012-02-14), fminunc.m does not work if the option "FunValCheck" is set to "on".


octave:1> fminunc (@ (x) x^2, 1, optimset ("FunValCheck", "on"))
error: `jx' undefined near line 353 column 33
error: evaluating argument list element number 1
error: called from:
error:   /home/olaf/devel/src/octave/scripts/optimization/fminunc.m at line 353, column 3
error:   /home/olaf/devel/src/octave/scripts/optimization/fminunc.m at line 149, column 6


This is due to a typo (probably after copy-and-paste from fsolve), jx is the gradient returned by the user function and should be named gx here. After correcting this:


octave:1> fminunc (@ (x) x^2, 1, optimset ("FunValCheck", "on"))
error: `complexeqn' undefined near line 355 column 11
error: called from:
error:   /home/olaf/devel/src/octave/scripts/optimization/fminunc.m at line 353, column 3
error:   /home/olaf/devel/src/octave/scripts/optimization/fminunc.m at line 149, column 6


This is again probably due to a copy-and-paste mistake, the option "ComplexEqn" is not applicable to fminunc (it expects a real scalar returned by the user function) and these two lines with the test should be deleted.

A small patch will be attached in the next comment, I want to get the bug number first.

Olaf Till <i7tiol>
Group Member

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #25067:  fix-bug-35534.changeset added by i7tiol (882B - application/octet-stream)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by i7tiol (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 4 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2012-02-18 rik5 StatusConfirmed Fixed
        Open/ClosedOpen Closed
    2012-02-15 rik5 StatusNone Confirmed
    2012-02-15 i7tiol Attached File- Added fix-bug-35534.changeset, #25067

    Back to the top

    Powered by Savane 3.13-02a9.
    Corresponding source code