一维搜索 – 编码无悔 / Intent & Focused

[原创] line search中的重要定理 - 梯度与方向的点积为零

2020 年 04 月 28 日2014 年 03 月 02 日作者 learnhard

对精确的line search（线搜索），有一个重要的定理：

这个定理表明，当前点在 ${d_k}$ 方向上移动到的那一点（ ${x_k} + {\alpha _k}{d_k}$ ）处的梯度，与当前点的搜索方向 ${d_k}$ 的点积为零。

[原创]使用一维搜索(line search)的算法的收敛性

2020 年 04 月 28 日2013 年 10 月 29 日作者 learnhard

在最优化领域中，有一类使用一维搜索（line search）的算法，例如牛顿法等。这类算法采用的是确定搜索方向→进行一维搜索→调整搜索方向→进行一维搜索的迭代过程来求解。那么，这类算法应该满足什么条件的时候才能收敛？本文将略为讨论一下。请务必看清本文的标题：不是讨论line search的收敛性，而是讨论使用line search的算法的收敛性。

[原创]一维搜索中的划界(Bracket)算法

2020 年 04 月 28 日2013 年 10 月 26 日作者 learnhard

很多最优化算法需要用到一维搜索（line search）子算法，而在众多的一维搜索算法中，大多数都要求函数被限制在一个内，也就是说，在进行一维搜索的区间内，函数是一个。尽管有一些改进的一维搜索算法（例如 $H\ddot opfinger$ 建议的一种改进过的黄金搜索算法）可以处理函数非单峰的情况，但是，在没有确定函数在一个区间内是单峰的之前，即使在搜索过程中，函数值持续减小，我们也不能说极小值是一定存在的，因此，找出一个区间，在此区间之内使函数是单峰的，这个过程是必需的（我更倾向于接受这种观点）。这个过程就叫作划界（Bracket）。Bracket这个单词是括号的意思，很形象——用括号包住一个范围，就是划界。在某些书中，划界算法也被称为进退法。