Commons Math
  1. Commons Math
  2. MATH-1092

NonLinearConjugateGradientOptimizer's Line search is a gradient search returns obviously suboptimal point.

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 3.3
    • Labels:
      None

      Description

      In package : org.apache.commons.math3.optim.nonlinear.scalar.gradient

      In a minimization problem, a line search should not return a point where the value is greater than the values at the edges of the interval. The line search violates this obvious requirement by focusing solely on solving for gradient=0 and ignoring the value.

      Moreover LineSearchFunction is something that can be used in other contexts, so perhaps this should be a standalone class.

        Activity

        Hide
        Gilles added a comment -

        Here is a proposal to factor out the "LineSearch" defined in "PowellOptimizer"
        (which uses "BrentOptimizer").
        When replacing what needed be in "NonlinearConjugateGradientOptimizer", a series of unit test started to fail.
        I've performed some checks that the convergence criterion is indeed met even though the result found is now farther from the expected optimum.

        The change also uncovered that by using the root solver, the optimizer could not correctly count the evaluations (cf. "MultiStartMultivariateOptimizerTest").

        Show
        Gilles added a comment - Here is a proposal to factor out the "LineSearch" defined in "PowellOptimizer" (which uses "BrentOptimizer"). When replacing what needed be in "NonlinearConjugateGradientOptimizer", a series of unit test started to fail. I've performed some checks that the convergence criterion is indeed met even though the result found is now farther from the expected optimum. The change also uncovered that by using the root solver, the optimizer could not correctly count the evaluations (cf. "MultiStartMultivariateOptimizerTest").
        Hide
        Luc Maisonobe added a comment -

        LineSearch seems to be missing in the patch.

        Show
        Luc Maisonobe added a comment - LineSearch seems to be missing in the patch.
        Hide
        Gilles added a comment -

        Oops...

        Show
        Gilles added a comment - Oops...
        Hide
        Luc Maisonobe added a comment -

        This seems good to me.

        The missing function evaluations count is probably due to the GradientMultivariateOptimizer.computeObjectiveGradient method,
        which lacks a call to incrementEvaluationCount() which is used for example in MultivariateOptimizer.computeObjectiveValue.

        I don't remember if this was intentional or not. Both computeObjectiveValue and computeObjectiveGradient are called in NonLinearConjugateGradientOptimizer.doOptimize, and computeObjectiveGradient was also called (and was the only function called)
        for the initial gradient-based line search. So we should probably also call incrementEvaluationCount for computeObjectiveGradient, and
        this will probably increase even more the total number of calls.

        Show
        Luc Maisonobe added a comment - This seems good to me. The missing function evaluations count is probably due to the GradientMultivariateOptimizer.computeObjectiveGradient method, which lacks a call to incrementEvaluationCount() which is used for example in MultivariateOptimizer.computeObjectiveValue. I don't remember if this was intentional or not. Both computeObjectiveValue and computeObjectiveGradient are called in NonLinearConjugateGradientOptimizer.doOptimize, and computeObjectiveGradient was also called (and was the only function called) for the initial gradient-based line search. So we should probably also call incrementEvaluationCount for computeObjectiveGradient, and this will probably increase even more the total number of calls.
        Hide
        Gilles added a comment -

        The missing function evaluations count is probably due to the GradientMultivariateOptimizer.computeObjectiveGradient method, [...]

        Oh, yes, you are right; I overlooked the "Gradient" part of the name...

        I don't remember if this was intentional or not.

        I recall that we indeed decided not to count the calls to that method.

        Anyway the "computeObjectiveGradient" is not called anymore in the new line search.
        Is that OK? I mean: Can the class still be considered a "standard" implementation of the algorithm?

        Show
        Gilles added a comment - The missing function evaluations count is probably due to the GradientMultivariateOptimizer.computeObjectiveGradient method, [...] Oh, yes, you are right; I overlooked the "Gradient" part of the name... I don't remember if this was intentional or not. I recall that we indeed decided not to count the calls to that method. Anyway the "computeObjectiveGradient" is not called anymore in the new line search. Is that OK? I mean: Can the class still be considered a "standard" implementation of the algorithm?
        Hide
        Bruce A Johnson added a comment -

        There is a good discussion in Numerical Recipes on using gradients in a line minimization (the conclusion being basically to use them very judiciously, for example to figure out what side of the interval to search in). Since we have gradients available there might be some advantage in optionally using them in the line minimization). For now, I'm quite happy that with your fix the line minimizer should never return a point with a higher value than the starting point (assuming we're doing minimization rather than maximization).

        Show
        Bruce A Johnson added a comment - There is a good discussion in Numerical Recipes on using gradients in a line minimization (the conclusion being basically to use them very judiciously, for example to figure out what side of the interval to search in). Since we have gradients available there might be some advantage in optionally using them in the line minimization). For now, I'm quite happy that with your fix the line minimizer should never return a point with a higher value than the starting point (assuming we're doing minimization rather than maximization).
        Hide
        Gilles added a comment -

        Code updated in revision 1572988.
        Could please check that it fixes your issue?

        Show
        Gilles added a comment - Code updated in revision 1572988. Could please check that it fixes your issue?
        Hide
        Bruce A Johnson added a comment -

        I've downloaded 3.3 snapshot with svn and switched my code to use it. Right now there seems to be a change elsewhere in 3.3 that is causing a problem before I get to my use of NonLinearConjugateGradientOptimizer. Trying to figure out now what the problem is.

        Show
        Bruce A Johnson added a comment - I've downloaded 3.3 snapshot with svn and switched my code to use it. Right now there seems to be a change elsewhere in 3.3 that is causing a problem before I get to my use of NonLinearConjugateGradientOptimizer. Trying to figure out now what the problem is.
        Hide
        Bruce A Johnson added a comment -

        The new line search works, but I think it needs one change. The old version used a BracketingStep parameter to set the initial search size. That is not used in the new LineSearch code, which has a hard-coded an upper limit of 1:
        bracket.search(f, goal, 0, 1);

        For my optimization problem I find (with both the old and new code) I need a much smaller upper limit (1.0e-5 for example). Otherwise the minimum found isn't as good. So I think it would be important to pass the BracketingStep parameter into the new new LineSearch code.

        Show
        Bruce A Johnson added a comment - The new line search works, but I think it needs one change. The old version used a BracketingStep parameter to set the initial search size. That is not used in the new LineSearch code, which has a hard-coded an upper limit of 1: bracket.search(f, goal, 0, 1); For my optimization problem I find (with both the old and new code) I need a much smaller upper limit (1.0e-5 for example). Otherwise the minimum found isn't as good. So I think it would be important to pass the BracketingStep parameter into the new new LineSearch code.
        Hide
        Gilles added a comment -

        Parameter added (revision 1573316).

        However, I'm worried that some unit tests for "PowellOptimizer" fail when this parameter is set to a small value (1e-8). Thus, for "PowellOptimizer", I've hard-coded the value to 1 so that the previous behaviour is retained.
        Maybe there is an interpendence between this value and the other parameters of "BracketFinder".

        In your problem, are there oscillations in the vicinity of the optimum?
        It is difficult for me to figure out to the appropriate improvements without a unit test.

        Show
        Gilles added a comment - Parameter added (revision 1573316). However, I'm worried that some unit tests for "PowellOptimizer" fail when this parameter is set to a small value (1e-8). Thus, for "PowellOptimizer", I've hard-coded the value to 1 so that the previous behaviour is retained. Maybe there is an interpendence between this value and the other parameters of "BracketFinder". In your problem, are there oscillations in the vicinity of the optimum? It is difficult for me to figure out to the appropriate improvements without a unit test.
        Hide
        Bruce A Johnson added a comment -

        Couldn't we have another constructor that takes a fourth argument (the initial upper limit for the bracket search). The current constructor could default to 1.0 for that value so existing tests would pass.

        The problem I'm working on is the energy minimization of a complex molecule. I'm sure there are many local minima and if the bracket is too large it finds a minimum that is not as good as one near the origin of the search. So it seems essential to be able to specify the size of the search region. (As an aside, I use the CMAESOptimizer to initially search in this complex landscape, but (when I can use gradients) the ConjugateGradientOptimizer is useful to quickly refine the solution.

        Show
        Bruce A Johnson added a comment - Couldn't we have another constructor that takes a fourth argument (the initial upper limit for the bracket search). The current constructor could default to 1.0 for that value so existing tests would pass. The problem I'm working on is the energy minimization of a complex molecule. I'm sure there are many local minima and if the bracket is too large it finds a minimum that is not as good as one near the origin of the search. So it seems essential to be able to specify the size of the search region. (As an aside, I use the CMAESOptimizer to initially search in this complex landscape, but (when I can use gradients) the ConjugateGradientOptimizer is useful to quickly refine the solution.
        Hide
        Bruce A Johnson added a comment -

        I'm referring to the constructor for the new LineSearch class.

        Show
        Bruce A Johnson added a comment - I'm referring to the constructor for the new LineSearch class.
        Hide
        Gilles added a comment -

        Couldn't we have another constructor [...]

        Why another constructor?
        "PowellOptimizer" does use 1 for the parameter.

        We should have units tests for "LineSearch". It could help to understand what is going on as the initial step gets smaller.

        Show
        Gilles added a comment - Couldn't we have another constructor [...] Why another constructor? "PowellOptimizer" does use 1 for the parameter. We should have units tests for "LineSearch". It could help to understand what is going on as the initial step gets smaller.
        Hide
        Bruce A Johnson added a comment -

        Another constructor so one could do:

        line = new LineSearch(this, relativeTolerance, absoluteTolerance,initialStep);

        where initialStep is the value set with BracketingStep in NonLinearConjugateGradientOptimizer

        I presume the BracketingStep parameter was added for a reason to NonLinearConjugateGradientOptimizer, but we've lost this capability in the new code. Setting a smaller initial step (than 1.0) is clearly necessary for actual use of my application, but I'm not sure I can easily represent this need in a unit test case.

        Show
        Bruce A Johnson added a comment - Another constructor so one could do: line = new LineSearch(this, relativeTolerance, absoluteTolerance,initialStep); where initialStep is the value set with BracketingStep in NonLinearConjugateGradientOptimizer I presume the BracketingStep parameter was added for a reason to NonLinearConjugateGradientOptimizer, but we've lost this capability in the new code. Setting a smaller initial step (than 1.0) is clearly necessary for actual use of my application, but I'm not sure I can easily represent this need in a unit test case.
        Hide
        Gilles added a comment -

        line = new LineSearch(this, relativeTolerance, absoluteTolerance,initialStep);

        But this is indeed what I did in revision 1573316 (as advertized a couple comments above)...

        Show
        Gilles added a comment - line = new LineSearch(this, relativeTolerance, absoluteTolerance,initialStep); But this is indeed what I did in revision 1573316 (as advertized a couple comments above)...
        Hide
        Bruce A Johnson added a comment -

        Aaaah, I missed that you actually added this. Thanks!.

        Show
        Bruce A Johnson added a comment - Aaaah, I missed that you actually added this. Thanks!.
        Hide
        Luc Maisonobe added a comment -

        Closing all resolved issue now available in released 3.3 version.

        Show
        Luc Maisonobe added a comment - Closing all resolved issue now available in released 3.3 version.

          People

          • Assignee:
            Unassigned
            Reporter:
            Ajo Fod
          • Votes:
            0 Vote for this issue
            Watchers:
            4 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development