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

 
 

bug #35534: fminunc: FunValCheck buggy

Submitted by:  Olaf Till <i7tiol>
Submitted on:  Wed 15 Feb 2012 01:44:00 PM UTC  
 
Category: NoneSeverity: 3 - Normal
Priority: 5 - NormalItem Group: Other
Status: FixedAssigned to: None
Originator Name: Olaf TillOpen/Closed: Closed
Release: devOperating System: GNU/Linux

Add a New Comment(Rich Markup)
   

You are not logged in

Please log in, so followups can be emailed to you.

 

(Jump to the original submission 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>
Project 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>
Project 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>
Project 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>
Project 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.

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

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

The patch is attached.

(file #25067)

Olaf Till <i7tiol>
Project 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".

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:

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>
Project Member

 

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

Attach File(s):
   
   
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
  • -unavailable- added by rik5 (Posted a comment)
  • -unavailable- added by i7tiol (Submitted the item)
  •  

    Do you think this task is very important?
    If so, you can click here to add your encouragement to it.
    This task has 0 encouragements so far.

    Only project members can vote.

     

    Please enter the title of George Orwell's famous dystopian book (it's a date):

     

     

    Follow 4 latest changes.

    Date Changed By Updated Field Previous Value => Replaced By
    Sat 18 Feb 2012 07:41:56 PM UTCrik5StatusConfirmed=>Fixed
      Open/ClosedOpen=>Closed
    Wed 15 Feb 2012 07:07:23 PM UTCrik5StatusNone=>Confirmed
    Wed 15 Feb 2012 01:48:41 PM UTCi7tiolAttached File-=>Added fix-bug-35534.changeset, #25067

    Back to the top


    Powered by Savane 3.1-cleanup1