You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@commons.apache.org by "Pascal Parraud (Created) (JIRA)" <ji...@apache.org> on 2011/12/01 10:37:40 UTC

[jira] [Created] (MATH-716) BracketingNthOrderBrentSolver exceeds maxIterationCount while updating always the same boundary

BracketingNthOrderBrentSolver exceeds maxIterationCount while updating always the same boundary
-----------------------------------------------------------------------------------------------

                 Key: MATH-716
                 URL: https://issues.apache.org/jira/browse/MATH-716
             Project: Commons Math
          Issue Type: Bug
    Affects Versions: 3.0
            Reporter: Pascal Parraud
            Priority: Minor


In some cases, the aging feature in BracketingNthOrderBrentSolver fails.
It attempts to balance the bracketing points by targeting a non-zero value instead of the real root. However, the chosen target is too close too zero, and the inverse polynomial approximation is always on the same side, thus always updates the same bracket.
In the real used case for a large program, I had a bracket point xA = 12500.0, yA = 3.7e-16, agingA = 0, which is the (really good) estimate of the zero on one side of the root and xB = 12500.03, yB = -7.0e-5, agingB = 97. This shows that the bracketing interval is completely unbalanced, and we never succeed to rebalance it as we always updates (xA, yA) and never updates (xB, yB).

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

[jira] [Updated] (MATH-716) BracketingNthOrderBrentSolver exceeds maxIterationCount while updating always the same boundary

Posted by "Luc Maisonobe (Updated) (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/MATH-716?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Luc Maisonobe updated MATH-716:
-------------------------------

    Assignee: Luc Maisonobe

The problem Pascal (who works with me) describes has already been encountered during the development of the algorithm. The solution found at that time seems to be insufficient. What happens is that in order to still gain a few digits while rebalancing the bracketing interval, we base our retargeting on the currently best solution. In this case, we set targetY = -yA/16 and fail to rebalance. Using the other bracket would improve rebalancing but waste evaluations as was observed during development. So its not a perfect solution either.

I think a compromise would be to attempt rebalancing with a progressively more aggressive target. We could start from the current setting (i.e -1/16 of the best bracket), and if we still update the same side, move towards larger targets.
                
> BracketingNthOrderBrentSolver exceeds maxIterationCount while updating always the same boundary
> -----------------------------------------------------------------------------------------------
>
>                 Key: MATH-716
>                 URL: https://issues.apache.org/jira/browse/MATH-716
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 3.0
>            Reporter: Pascal Parraud
>            Assignee: Luc Maisonobe
>            Priority: Minor
>
> In some cases, the aging feature in BracketingNthOrderBrentSolver fails.
> It attempts to balance the bracketing points by targeting a non-zero value instead of the real root. However, the chosen target is too close too zero, and the inverse polynomial approximation is always on the same side, thus always updates the same bracket.
> In the real used case for a large program, I had a bracket point xA = 12500.0, yA = 3.7e-16, agingA = 0, which is the (really good) estimate of the zero on one side of the root and xB = 12500.03, yB = -7.0e-5, agingB = 97. This shows that the bracketing interval is completely unbalanced, and we never succeed to rebalance it as we always updates (xA, yA) and never updates (xB, yB).

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

[jira] [Resolved] (MATH-716) BracketingNthOrderBrentSolver exceeds maxIterationCount while updating always the same boundary

Posted by "Luc Maisonobe (Resolved) (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/MATH-716?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Luc Maisonobe resolved MATH-716.
--------------------------------

       Resolution: Fixed
    Fix Version/s: 3.0

Fixed in subversion repository as of r1209307.

Thanks for the report.
                
> BracketingNthOrderBrentSolver exceeds maxIterationCount while updating always the same boundary
> -----------------------------------------------------------------------------------------------
>
>                 Key: MATH-716
>                 URL: https://issues.apache.org/jira/browse/MATH-716
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 3.0
>            Reporter: Pascal Parraud
>            Assignee: Luc Maisonobe
>            Priority: Minor
>             Fix For: 3.0
>
>
> In some cases, the aging feature in BracketingNthOrderBrentSolver fails.
> It attempts to balance the bracketing points by targeting a non-zero value instead of the real root. However, the chosen target is too close too zero, and the inverse polynomial approximation is always on the same side, thus always updates the same bracket.
> In the real used case for a large program, I had a bracket point xA = 12500.0, yA = 3.7e-16, agingA = 0, which is the (really good) estimate of the zero on one side of the root and xB = 12500.03, yB = -7.0e-5, agingB = 97. This shows that the bracketing interval is completely unbalanced, and we never succeed to rebalance it as we always updates (xA, yA) and never updates (xB, yB).

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

        

[jira] [Commented] (MATH-716) BracketingNthOrderBrentSolver exceeds maxIterationCount while updating always the same boundary

Posted by "Luc Maisonobe (Commented) (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/MATH-716?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13161241#comment-13161241 ] 

Luc Maisonobe commented on MATH-716:
------------------------------------

The following simple test reproduces the bad behavior with a trivial function:
{code}
    @Test
    public void testIssue716() {
        BracketingNthOrderBrentSolver solver =
                new BracketingNthOrderBrentSolver(1.0e-12, 1.0e-10, 0.0, 5);
        UnivariateFunction sharpTurn = new UnivariateFunction() {
            public double value(double x) {
                return (2 * x + 1) / (1.0e9 * (x + 1));
            }
        };
        double result = solver.solve(100, sharpTurn, -0.9999999, 30, 15, AllowedSolution.RIGHT_SIDE);
        Assert.assertEquals(0, sharpTurn.value(result), solver.getFunctionValueAccuracy());
        Assert.assertTrue(sharpTurn.value(result) >= 0);
        Assert.assertEquals(-0.5, result, 1.0e-10);
    }
{code}
The test fails with TooManyEvaluationsException. In fact, only the right side of the bracketing interval is updated and very slowly decreases from 15.0 to 14.999677603318897 while the left side of the bracketing interval is stuck at -0.9999999.
                
> BracketingNthOrderBrentSolver exceeds maxIterationCount while updating always the same boundary
> -----------------------------------------------------------------------------------------------
>
>                 Key: MATH-716
>                 URL: https://issues.apache.org/jira/browse/MATH-716
>             Project: Commons Math
>          Issue Type: Bug
>    Affects Versions: 3.0
>            Reporter: Pascal Parraud
>            Assignee: Luc Maisonobe
>            Priority: Minor
>
> In some cases, the aging feature in BracketingNthOrderBrentSolver fails.
> It attempts to balance the bracketing points by targeting a non-zero value instead of the real root. However, the chosen target is too close too zero, and the inverse polynomial approximation is always on the same side, thus always updates the same bracket.
> In the real used case for a large program, I had a bracket point xA = 12500.0, yA = 3.7e-16, agingA = 0, which is the (really good) estimate of the zero on one side of the root and xB = 12500.03, yB = -7.0e-5, agingB = 97. This shows that the bracketing interval is completely unbalanced, and we never succeed to rebalance it as we always updates (xA, yA) and never updates (xB, yB).

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira