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

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

阅读更多

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

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

阅读更多