Why is line search not popular in quasi-Newton geometry optimisers?

One of the most important quasi-Newton optimisation methods is the BFGS (which uses an iterated Hessian update scheme to avoid recalculation of the actual Hessian). Most numerical optimisation packages such as scipy (code here) use line searches with the BFGS search direction.

However, molecular geometry optimisers, which are also based on the same principle, usually do not use a line search, instead they constrain the step size with a trust radius. This is also the case with optimisers used with NEB such as L-BFGS-B. Overall, accurate line search does not seem to exist in computational chemistry as much as it does in maths or other fields where optimisation is necessary. I did read some very old (1980's) computational papers where they replace accurate line search with a line search on a fitted polynomial surface.

Is it because evaluating gradient and energies are expensive (for accurate line search)? And that using line search would be expensive overall instead of just using a trust radius to scale back the step? Most importantly, is there a benchmark or something similar that shows the difference between using line search and trust radius?

Note that I am talking about accurate line search (such as Wolfe or Armijo line search), not line search on a fitted polynomial surface (which some optimisers like Gaussian do).

• CASTEP does use an advanced line search algorithm for its geometry optimization task.
– Sha
Commented Mar 31, 2023 at 13:55

A trust region method is not really a replacement for a line-search optimisation, the methods are complementary.

A line-search optimiser would usually proceed by taking a trial step in the direction of the (preconditioned) forces, and then evaluating the new energies and forces (and possibly stresses) at that trial configuration. Using this new information, the optimiser would then calculate a better step length to use. Of course, you will never get the exact optimal step, so a better step can always be found; how do you know whether your step is "good enough", or whether you should keep trying for a better step? This is where the Wolfe conditions come in. The Wolfe conditions do not describe an exact optimiser, they are precisely designed to help your inexact optimiser to converge efficiently to the solution. Evaluating energies and gradients is computationally demanding, and we don't want to do it more than we have to.

Given our line-search method, why might me want to use a trust region approach? Well, what if we start a very long way from our minimum, and perhaps our preconditioner is not very good. We could find that our initial trial step takes us to a completely different region of phase space, with a different local minimum to the one we want.

For example, suppose we have a ferromagnetic material, but the atoms are too far apart. Our trial step could move the atoms too close together, and this could cause some of the spins to be suppressed, pushing the material to a nonmagnetic state; or some of the spins might even flip, making an antiferromagnetic phase. The next optimisation step will move the atoms further apart again, but they might stay in this new magnetic state, and not the ferromagnetic state we wanted.

This problem occurred because our trial step moved the atoms outside the region of space that our (preconditioned) optimiser modelled reliably; we moved out of the "trust region". Trust region methods estimate the region of configuration space in which our optimiser can be trusted, and if the trial step would take us out of that region, they reduce the trial step to take us just to the boundary of the trust region. This stops the method taking you into completely different regions of configuration space accidentally.

Once the new step has been taken, the new energies and forces are included in the optimiser model (e.g. the BFGS Hessian) and the trust region is recalculated. In this way, the atoms are allowed to move into a different state if that is genuinely the low energy, zero-force solution, but they won't do it just by accidentally moving too far -- or that's the idea, anyway!

Of course, if your trial step stays within the trust region, then the usual line-search optimisation can be used to find a good enough step to take.

• Thanks, that clears up some of my questions. But I still want to know why accurate line search is not done in most QM softwares like ORCA, GAMESS, Gaussian etc.? i.e. is using a trust radius alone enough? (Unless line search is done and I am missing something!) Commented Apr 3, 2023 at 12:59
• @SRMaiti I can't help there, I'm afraid, I work with materials modelling software, and as far as I know they all do a line search. Are you sure Gaussian doesn't use a line search? Commented Apr 3, 2023 at 22:09
• Gaussian uses a polynomial fitted line search, not accurate line search as far as I know, but their software is not open source so not 100% sure. Commented Apr 4, 2023 at 8:49
• @SRMaiti I expect everyone does a polynomial fit, possibly with a bisection search as a fallback; I don't understand why you think that isn't accurate? The energy surface is generally smooth, continuous and differentiable, so a polynomial fit should be good. Commented Apr 5, 2023 at 0:50
• I don't mean that it is inaccurate as in wrong numbers, I guess I mean as in not rigorously following the math (?) Commented Apr 5, 2023 at 8:48