Rurainski Alexander, Hildebrandt Andreas, Lenhof Hans-Peter
Center for Bioinformatics, Saarland University, 66123 Saarbrücken, Germany.
J Comput Chem. 2009 Jul 15;30(9):1499-509. doi: 10.1002/jcc.21175.
Force field based energy minimization of molecular structures is a central task in computational chemistry and biology. Solving this problem usually requires efficient local minimization techniques, i.e., iterative two-step methods that search first for a descent direction and then try to estimate the step width. The second step, the so called line search, typically uses polynomial interpolation schemes to estimate the next trial step. However, dependent on local properties of the objective function alternative schemes may be more appropriate especially if the objective function shows singularities or exponential behavior. As the choice of the best interpolation scheme cannot be made a priori, we propose a new consensus line search approach that performs several different interpolation schemes at each step and then decides which one is the most reliable at the current position. Although a naive consensus approach would lead to severe performance impacts, our method does not require additional evaluations of the energy function, imposing only negligible computational overhead. Additionally, our method can be easily adapted to the local behavior of other objective functions by incorporating suitable interpolation schemes or omitting non-fitting schemes. The performance of our consensus line search approach has been evaluated and compared to established standard line search algorithms by minimizing the structures of a large set of molecules using different force fields. The proposed algorithm shows better performance in almost all test cases, i.e., it reduces the number of iterations and function and gradient evaluations, leading to significantly reduced run times.
基于力场的分子结构能量最小化是计算化学和生物学中的核心任务。解决这个问题通常需要高效的局部最小化技术，即迭代两步法，该方法首先搜索下降方向，然后尝试估计步长。第二步，即所谓的线性搜索，通常使用多项式插值方案来估计下一个试验步长。然而，根据目标函数的局部性质，替代方案可能更合适，特别是当目标函数表现出奇异性或指数行为时。由于无法事先选择最佳插值方案，我们提出了一种新的共识线性搜索方法，该方法在每一步执行几种不同的插值方案，然后确定在当前位置哪一种方案最可靠。虽然简单的共识方法会导致严重的性能影响，但我们的方法不需要对能量函数进行额外评估，只会带来可忽略不计的计算开销。此外，通过纳入合适的插值方案或省略不适用的方案，我们的方法可以很容易地适应其他目标函数的局部行为。我们通过使用不同的力场最小化一大组分子的结构，对我们的共识线性搜索方法的性能进行了评估，并与既定的标准线性搜索算法进行了比较。所提出的算法在几乎所有测试案例中都表现出更好的性能，即它减少了迭代次数以及函数和梯度评估次数，从而显著缩短了运行时间。
