Too many iterations while solving with BracketingNthOrderBrentSolver

Hipparchus usage
1

Hello,

We are encountering some difficulties to use BracketingNthOrderBrentSolver. We have found that the solver continue iterations even after finding a solution.
It is like it searches for more precise solution besides the accuracy required at initialization.

This is a problem in our case because the function is executing some heavy/long computations and we cannot afford some extra iterations.

We have written a junit test to demonstrate the problem :

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
import org.hipparchus.analysis.UnivariateFunction;
import org.hipparchus.analysis.solvers.BracketingNthOrderBrentSolver;
import org.hipparchus.util.FastMath;
import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class HipparchusSolverTest {

    private static class FunctionHipparcus implements UnivariateFunction {

        List<Double> values = new ArrayList<>();

        @Override
        public double value(double x) {
            double value = -0.01 * x * x + 20;
            values.add(value);
            return value;
        }
    }

    public static final double ABSOLUTE_ACCURACY = 0.1;
    private static final double VALUE_ACCURACY = 1.;

    @Test
    public void testSolverStopIteratingOnceSolutionIsFound() {
        BracketingNthOrderBrentSolver solver = new BracketingNthOrderBrentSolver(1e-14, ABSOLUTE_ACCURACY, VALUE_ACCURACY, 5);
        FunctionHipparcus function = new FunctionHipparcus();
        solver.solve(100, function, -100, 100);
        Assertions.assertEquals(1, function.values.stream().filter(value -> FastMath.abs(value) < VALUE_ACCURACY).count(), // 
                                () -> String.format("Too many iterations : \n%s\n",
                                                    function.values.stream().map(value -> String.format("%f.3", value)).collect(Collectors.joining("\n"))));
    }
}

It might be because of the relative accuracy ? We have tried some several relative accuracy but it is hard to find a relative accuracy that allow to find a solution below the value accuracy and without over-iterating.

Could you help us ? Do you think it is a bug or a bad use ?

Best regards,

Anne-Laure

2

It was a bug!
I have registered it as issue 183.

The problem comes from the solutions selection settings. As BracketingNthOrderBrentSolver implements BracketedUnivariateSolver, it has a setting for allowed solutions in the form of the AllowedSolution enumerate and during its search it maintains an interval that brackets the solution (hence the names). The enumerate allows for example users to specify they always want a solution at the right of the true zero, which is important for example for events detection in Ordinary Differential Equations integration (or they can select the left hand side, or positive values, or negative values, or the boundary closest to zero).

BracketingNthOrderBrentSolver then first reduces the interval until either it finds an exact zero (in which case it returns a zero-length interval as soon as it finds the zero) or until both values at boundaries or interval length are below their respective threshold. Once the interval has been found, then it selects one of the boundary according to the enumerate.

In your case, as you did not specify the enumerate, you got the default value which is AllowedSolution.ANY_SIDE. This settings corresponds to the selection of the boundary that as a value closest to zero. So in this case, it would be sufficient to return as soon as one value is below function threshold, as it will be the solution selected, but this is not the current behavior: we continue calling the function until the other side of the interval is also within threshold, thus wasting computing time.

I have fixed the problem in the develop branch. Could you check if it works for you?

3

Thank you so much for your reply and for the fix! That was fast, I only regret we did not post here before… :slight_smile:!

Best regards,