With Gabor Csanyi and James Kermode I have been developing bespoke algorithms for molecular geometry optimisation. The three main thrusts of this research are (1) preconditioners [75, 74, 59]; (2) effective line-search heuristics [75, 55]; and (3) saddle point search [75, 64, 55].
Consider a smooth potential energy landscape . Computing (local) minima is an extremely well-studied and well-understood problem. For example, the steepest descent method
with suitable step-size selection is guaranteed to converge at least to a critical point, which will "likely" be a local minimum. More sophisticated methods that use curvature information can even theoretically prevent convergence critical points that are not minima. The key point that makes this possible is that a reduction in energy in an optimisation step is already sufficient to guarantee convergence.
A simple saddle point search method related to steepest descent are the dimer/GAD methods. The idea is to augment the state with a direction variable and derive a dynamical system whose stable equilibria are precisely the index-1 saddle points
The idea is that follows a gradient flow for the Rayleigh quotient and hence convergence to the minimal eigenvalue, while follows a gradient flow in all directions orthogonal to but moves uphill in the -direction. To implement this idea we discretise in time,
It is easy to show that if is sufficiently small and start near a stable index-1 saddle, then the iterates converge to a saddle point.
Open Problem: Global convergence, on the other hand is entirely open: the challenge stems from the fact that there is no obvious "merit function" (e.g., Lyapunov functional) whose minima are the index-1 saddle points. In fact, Antoine Levitt and I showed in [64] that there exists no merit function for which the dimer/GAD direction is a descent direction.
Most of my work on this topic has been on practical aspects of saddle point search, i.e., developing heuristics that perform well in practise, e.g.,
Modulated Newton methods (in preparation)
But the most interesting and most challenging question is whether it is possible to develop algorithms that are guaranteed to compute a saddle point. The most promising approach to achieve this is via the path-based methods, i.e., computing a path that connects two energy minima, such as the String and NEB methods. But these methods come (a) at a significantly increased computational cost; and (b) come with other significant analytical challenges. For "walker" methods such as dimer/GAD it is even unclear on a heuristic level whether globally convergent variants exist.
My work on preconditioners focuses on molecular potential energy landscapes and is primarily application-driven. The main idea can be explained as follows: The asymptotic convergence rate of the steepest descent method,
is roughly where is the condition number of and
. Ill-conditioning () enters molecular PESs in a variety of ways, such as large materials systems where the ratio of highest and lowest wave-numbers becomes large, or large ratios between bond-stiffness in bio-molecules.
In the preconditioned steepest descent method, the iterates are
and the convergence rate is now determined by the preconditioned hessian instead of . Of course, one can (and should) apply preconditioning ideas to most optimisation algorithms, not only steepest descent, in particular we typically use LBFGS or CG variants in practise.
To construct a preconditioner, we begin with a surrogate PES , possibly , but in important cases e.g. when is given by an electronic structure model this is no longer possible. We then modify the hessian expression in a way that yields a new matrix but which remains positive definite throughout the entire PES. The idea is best illustrated at the example of a pair potential:
Let
then
We then specify the preconditioner my making positive each "local" hessian rather than the global hessian , that is, we define
This guarantees that will be positive, hence we can set in the preconditioned steepest descent method.
This construction can be readily generalised to a wide range of bond types and optimisation schemes; see [75, 74, 59] for the details and prototype applications.