bugGNU Octave - Bugs: bug #41146, fsolve failure

 
 

bug #41146: fsolve failure

Submitted by:  Harshal Vora <harshal_vora>
Submitted on:  Wed 08 Jan 2014 10:39:43 AM UTC  
 
Category:  Octave Function Severity:  3 - Normal
Priority:  5 - Normal Item Group:  Incorrect Result
Status:  Fixed Assigned to:  None
Originator Name:  Harshal Vora Open/Closed:  Closed
Release:  dev Operating 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)

Thu 02 Aug 2018 06:01:36 PM UTC, comment #9: 

I overhauled fsolve.m in this changeset (https://hg.savannah.gnu.org/hgweb/octave/rev/bf89eea6652e).

Part of the overhaul involved changing the way Octave calculates the Jacobian using finite differences.  The new algorithm, I believe, matches Matlab and it leads to taking larger step sizes which makes convergence quicker.

I also changed the following fsolve options to match Matlab

TolX -> 1e-6 from 1e-7
TolFun -> 1e-6 from 1e-7
FinDiffType -> "forward" from "central"
"Updating -> "off" from "on"
"MaxFunEvals -> 100*number_of_variables from Inf

Taken together, fsolve is almost able to solve the original poster's problem with default options.  The only issue is that MaxFunEvals is set to 300 because there are three unknown variables, but the solver requires 346 function evaluations to converge.  I don't think this qualifies as "fsolve failure" anymore.  If attempting the solution from scratch, fsolve would report an exit code of 0 (maximum iterations exceeded).  A cognizant user would then simply double MaxFunEvals to see if throwing more computes at it would solve the problem, and it would.

Marking as fixed and closing report.

Rik <rik5>
Project Administrator
Fri 25 Nov 2016 11:03:43 PM UTC, comment #8: 

This issue is still present in Octave 4.2.0.

The result of the problem in comment #0 is now the following, so our solver still fails here (with default solver settings).

x =

    -88.308
  -2111.868
    -13.814

fval =

   -7.6648
  -10.6501
   18.3508

info = 0

Hartmut <hardy>
Thu 09 Jan 2014 03:27:04 PM UTC, comment #7: 

The algorithm has changed several times.  In Octave 3.0.x, Octave used MINPACK.  In 3.2.x, Jaroslav rewrote fsolve as a .m file.  With 3.2.4, fsolve does max out on iterations, but it also gets close to the solution.  With 3.6.4, it maxes out on iterations but is nowhere near the solution.  When we switched from MINPACK to Jaroslav's fsolve, we noticed that a number of problems that MINPACK could solve could not be solved by the new fsolve.  Some of those were fixed, others are still problems.  FWIW, I tried 3.0.5 with the problem in this report and it failed.

It appears that Matlab now offers several different solvers under the function name fsolve (selected by an option) and that the default solver can solve this problem.  So I reopened this bug report, changed the release to "dev", set the item group to incorrect result instead of regression, and changed the summary to just be "fsolve failure"

John W. Eaton <jwe>
Project Administrator
Thu 09 Jan 2014 06:17:55 AM UTC, comment #6: 

Thanks.
Makes sense if the algorithm changed.

Regards,

Harshal Vora <harshal_vora>
Thu 09 Jan 2014 06:10:51 AM UTC, comment #5: 

I believe the algorithm changed between 3.2.X and 3.4.X so that would explain the difference.  Versions 3.4.X, 3.6.X, and 3.8.0 all produce the same result for the same input.

Determining the optimum starting point depends critically on the function to be solved.  As far as I know there is no general method for selecting the initial point.  Obviously if you have an idea of where the solution point lies (from past experience, perhaps graphing of the equations if the dimensionality of the problem is not too high) then using that point will likely yield good results and the convergence will be quick.

Rik <rik5>
Project Administrator
Thu 09 Jan 2014 05:47:22 AM UTC, comment #4: 

Hi,

Thanks for the reply.
I will upgrade to the latest version.

I agree to you that according to the INFO value, my answers have not converged, but at the same time shouldnt we expect the same result (same return code and final values of x) from two different versions of octave for the same set of equations and same starting points?

Also, is there any way we can determine the starting points to be selected to get optimum results?

Regards,

Harshal Vora <harshal_vora>
Thu 09 Jan 2014 05:26:57 AM UTC, comment #3: 

First, versions 3.2 and 3.4 are absolutely ancient and are no longer supported.  You want to upgrade to 3.8 which is the latest stable release.  See the downloads page (http://www.gnu.org/software/octave/download.html).

Have a look at the documentation for fsolve by using

help fsolve

from within Octave.

The INFO code from fsolve tells whether the algorithm succeeded or not.  From the documentation

On return, FVAL contains the value of the function FCN evaluated
    at X, and INFO may be one of the following values:

   1
         Converged to a solution point.  Relative residual error is
         less than specified by TolFun.

   2
         Last relative step size was less that TolX.

   3
         Last relative decrease in residual was less than TolF.

   0
         Iteration limit exceeded.

   -3
         The trust region radius became excessively small.

So for 3.2.4 the return code was 0 which means that the algorithm did not converge because the iteration limit was exceeded.  The fact that the answer looks better is not meaningful since the return code says that the algorithm failed.  For version 3.4.3 the return code was 3 which is also a failure.

Like most optimization algorithms, the solver is sensitive to the initial point where you begin searching from.  I got the algorithm to converge by changing the initial point and allowing it to run a bit longer with more iterations.

[x, fval, info] = fsolve (@f, [1; 0; 0], optimset ("MaxIter", 1e3))
x =

    8.1103
    8.2196
  -76.6589

fval =

   2.8548e-10
   3.0565e-09
   7.3383e-06

info =  1

This isn't a bug in Octave, just normal variation with respect to convergence for a non-linear solver.

Rik <rik5>
Project Administrator
Wed 08 Jan 2014 03:49:27 PM UTC, comment #2: 

I have attached a file named octave_function_with_bug

Regards,

Harshal Vora <harshal_vora>
Wed 08 Jan 2014 02:38:25 PM UTC, comment #1: 

The rich-text markup feature of the text box in the bug tracker ate some of your code.  Could you please post it as an attachment instead?

John W. Eaton <jwe>
Project Administrator
Wed 08 Jan 2014 10:39:43 AM UTC, original submission:  

Hi,

I happen to install Octave on two different machines, one ubuntu and another centOS.
I installed octave from apt-get and yum repositories respectively.
Ubuntu is a 64 bit machine and has version 3.2.4
CentOS is a 32 bit machine and has version 3.4.3

When I run the following function

function y = f(x);y = zeros (3,1);y(1) = -88.0 + 20.0*log10(sqrt((8.5-x(1))^2+(4.55-x(2))^2+(0.0-0)^2))- x(3);y(2) = -91.0 + 20.0*log10(sqrt((2.9-x(1))^2+(8.375-x(2))^2+(0.0-0)^2))- x(3);y(3) = -62.0 + 20.0*log10(sqrt((8.01-x(1))^2+(8.375-x(2))^2+(0.0-0)^2))- x(3);endfunction; [x, fval, info] = fsolve (@f, [1; 1; 1])

I get two different outputs on each machine.

Output on ubuntu (v 3.2.4)

x =

    8.1690
    8.2760
  -76.5510

fval =

   0.0099340
  -0.0128684
   0.0030655

info = 0

Output on centOS (v 3.4.3)

x =

   -317.530
  -1605.336
    -15.975

fval =

   -7.7144
  -10.7004
   18.3049

info =  3

--------------

Output from Ubuntu (64bit, v 3.2.4) is correct. Is this a bug in the newer release?

---------------

Version info:

Ubuntu

CentOSoctave -v
GNU Octave, version 3.2.4
Copyright (C) 2009 John W. Eaton and others.
This is free software; see the source code for copying conditions.
There is ABSOLUTELY NO WARRANTY; not even for MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.

Octave was configured for "x86_64-pc-linux-gnu".

Additional information about Octave is available at http://www.octave.org.

Please contribute if you find this software useful.
For more information, visit http://www.octave.org/help-wanted.html

Report bugs to <bug@octave.org> (but first, please read
http://www.octave.org/bugs.html to learn how to write a helpful report).

$ octave -v
GNU Octave, version 3.4.3
Copyright (C) 2011 John W. Eaton and others.
This is free software; see the source code for copying conditions.
There is ABSOLUTELY NO WARRANTY; not even for MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.

Octave was configured for "i386-redhat-linux-gnu".

Additional information about Octave is available at http://www.octave.org.

Please contribute if you find this software useful.
For more information, visit http://www.octave.org/help-wanted.html

Read http://www.octave.org/bugs.html to learn how to submit bug reports.

Harshal Vora <harshal_vora>

 

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

Attach Files:
   
   
Comment:
   

Attached Files
file #30222:  octave_function_with_bug added by harshal_vora (325B - application/octet-stream - File with octave function attached.)

 

Depends on the following items: None found

Items that depend on this one: None found

 

Carbon-Copy List
  • -email is unavailable- added by hardy (Posted a comment)
  • -email is unavailable- added by rik5 (Posted a comment)
  • -email is unavailable- added by jwe (Posted a comment)
  • -email is unavailable- added by harshal_vora (Submitted the item)
  •  

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

    Only project members can vote.

     

     

     

    Follow 9 latest changes.

    Date Changed by Updated Field Previous Value => Replaced by
    2018-08-02 rik5 StatusNone => Fixed
        Open/ClosedOpen => Closed
    2014-01-09 jwe StatusInvalid => None
        Open/ClosedClosed => Open
        Release3.4.3 => dev
        SummaryDifferent results for fsolve in version 3.4.3 vs. 3.2.4 => fsolve failure
    2014-01-09 rik5 StatusNone => Invalid
        Open/ClosedOpen => Closed
    2014-01-08 harshal_vora Attached File- => Added octave_function_with_bug, #30222

    Back to the top


    Powered by Savane 3.5