Convergence and Cycling in Walker-type Saddle Search Algorithms
Convergence and Cycling in Walker-type Saddle Search Algorithms
复制标题
DOI：
10.1137/16m1087199
复制
发表时间：
2016-07
期刊：
影响因子：
--
通讯作者：
A. Levitt;C. Ortner
中科院分区：
文献类型：
--
作者：
A. Levitt;C. Ortner
光滑目标函数局部极小值的求解算法理论成熟，算法实现稳健高效。相比之下，鞍形搜索的理论和实践是贫乏的。在本文中，我们提出了二聚体和最平缓上升（GAD）鞍搜索算法的理想化版本的结果，这些结果展示了当前一类鞍搜索算法在理论上可实现的局限性：（1）给出了鞍吸引域的改进估计，（2）给出了GAD型动力学无法逃脱的势能威尔斯阱的具体例子，（3）对动力学陷入的“奇点”进行了局部分析，证明了拟周期解的存在性.这些结果表明，它是不可能获得的二聚体和GAD型算法的全局收敛的变种。
Algorithms for computing local minima of smooth objective functions enjoy a mature theory as well as robust and efficient implementations. By comparison, the theory and practice of saddle search is destitute. In this paper, we present results for idealized versions of the dimer and gentlest ascent (GAD) saddle search algorithms that showcase the limitations of what is theoretically achievable within the current class of saddle search algorithms: (1) we present an improved estimate on the region of attraction of saddles, (2) we give explicit examples of potential energy wells from which GAD-type dynamics are unable to escape, and (3) we present a local analysis of “singular points” around which the dynamics gets trapped and prove the existence of quasi-periodic solutions. These results indicate that it is impossible to obtain globally convergent variants of dimer- and GAD-type algorithms.