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

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

【1】什么是单峰区间?什么是单峰函数?
从字面上理解,“单峰”即函数只有一个峰,如下图所示(在区间[-8,8]内是单峰的):

文章来源:http://www.codelast.com/
而下面的这个函数,在区间[2,14]内就不是单峰函数了:

现在,我们再用数学的话来定义一下单峰区间和单峰函数:
[a,b]R 的子集,存在 {\alpha ^*} \in [a,b] ,使得 f(\alpha )[a,{\alpha ^*}] 上严格单调减,在 [{\alpha ^*},b] 上严格单调增,则称 [a,b]f(\alpha ) 的单峰区间, f(\alpha )[a,b] 上的单峰函数。
文章来源:http://www.codelast.com/
【2】“划界”是如何实现的
方法是:寻找使函数值达到“高→低→高”的3个点

如上图所示,当我们找到 a,b,c 这样3个点的时候,它们就能确定一个单峰区间了。
一定有人会有疑问说:这不一定,万一 b,c 之间还有一个峰怎么办?确实,这里举的例子并不是一个完善的例子,在一个实用的划界程序中,它所做的考虑会非常多,各种意外情况都要处理,此处只是为了说明“划界”是怎么一回事,以及一个最简单的划界程序是怎么做的。
文章来源:http://www.codelast.com/
与各种教科书上仅有令人讨厌的公式说明不同(从不考虑读者的感受),我把几个简单的划界步骤画成了几幅图,我觉得有小学文凭已经足够理解了(一图胜千言):

文章来源:http://www.codelast.com/
起始点为 {x_0} ,假设一开始向右寻找,步长为 h ,图中的 k 表示迭代的次数。
则第一点挪动到了 {x_1} = {x_0} + h ,计算函数值,发现 f({x_1}) < f({x_0}) ,很好,“高→低→高”的3点中,我们已经有了两点。
然后下一点我们挪动到 {x_2} = {x_1} + t \times h,\;t > 1 ,这里用加倍系数 t 来乘以步长是为了加速搜索的过程。再计算函数值,发现 f({x_2}) > f({x_1}) ,很好,我们已经找到了“高→低→高”的3点。任务完成, [a,b] 即为所求区间。
总结一下步骤就是:
{x_1} = {x_0} + h
{x_2} = {x_1} + t \times h
文章来源:http://www.codelast.com/

如果运气没那么好,例如:

文章来源:http://www.codelast.com/
即:
和①一样,搜索也经历了 {x_0},{x_1},{x_2} 这几个点,与①不同的是,到了 {x_2} 点之后,我们发现其函数值仍然小于 {x_1} 点处的函数值,也就是说,我们还没有找到“高→低→高”的3点。
于是我们继续放大步长,令 {x_3} = {x_2} + t \times t \times h ,再计算函数值,发现 f({x_3}) > f({x_2}) ,很好,我们已经找到了“高→低→高”的3点。任务完成, [a,b] 即为所求区间。
总结一下步骤就是:
{x_1} = {x_0} + h
{x_2} = {x_1} + t \times h (加大步长)
{x_3} = {x_2} + t \times t \times h (继续加大步长)
文章来源:http://www.codelast.com/

①是向右搜索,如果我们运气更差一些,一开始就是个错误(应该向左搜索),怎么办?

文章来源:http://www.codelast.com/
如上图,起始点为 {x_0} ,第一个挪动到的点起始点为 {x_1} ,而 {x_1} 处的函数值竟然比起始点 {x_0} 处的函数值要大(函数值不降反升)。于是我们可以向左搜索(将步长 h 设为负值),并且把 {x_1} 挪到 {x_0} ,继续按①的节奏进行下去。
总结一下步骤就是:
{x_1} = {x_0} + h (发现函数值不降反升)
h' = - h (步长设为负值,向左搜索)
{x_1} = {x_0} (重置 {x_1} 点)
{x_2} = {x_1} + h'
{x_3} = {x_2} + t \times h' (加大步长,函数值回升,停止搜索)
文章来源:http://www.codelast.com/
【3】加快划界的速度:逆抛物内插
有没有什么办法可以加快划界的速度呢?有,逆抛物内插Inverse Parabolic Interpolation)就是一种技术,它可以使得划界算法超线性收敛
为了解释什么是逆抛物内插,这里用书上的一幅图来讲解:

文章来源:http://www.codelast.com/
如图,实线为目标函数曲线。在该曲线上,如果我们要尽快逼近极小值点,可以这样做:通过①②③三点作一条抛物线(图中粗虚线所示),可以计算出该抛物线的极小值点的横坐标,从而可以找到同一横坐标下,目标函数上的点,即点④;然后再过①②④三点作一条抛物线(图中细虚线所示),可以计算出该抛物线的极小值点的横坐标,从而又可以找到同一横坐标下,目标函数上的点,即点⑤。这样,我们就很快地逼近了极小值。

那么,过三点的抛物线,其极小值点的横坐标怎么求?
已知函数 f(x) ,过 f(a),f(b),f(c) 三点的抛物线,其极小值点的横坐标 x 为:

文章来源:http://www.codelast.com/
注:为什么叫“”?因为上面的方法是用来求横坐标 x ,而不是求 y 的。

有人会问:划界的目标就是找到3个点,而你怎么会预先知道3个点的坐标,从而进行逆抛物内插?这不是因果倒置了吗?
其实,这里的三个点,并不是划界的结果,而是初始的猜测,通过初始的猜测点进行逆抛物内插,再根据内插点的不同情况,分别作不同的处理,最终可以找到划界的3个点。
例如,我们总要知道两个初始点 a,b 吧?好吧,如果你已知的真的只有一个点 a ,那么 b 就随便取比 a 大一点的值好了,这也能凑够两个点啊。通过这两个点,可以通过 c = b + COE \times (b - a) 来得到猜测的第一个 c 点(这里的 COE 表示一个系数,例如1.618),从而可以通过这3点开始逆抛物内插。
文章来源:http://www.codelast.com/
一个实用的划界程序还是挺复杂的——这里的复杂是比较于上面陈述的最简单的划界算法来说的,因为要保证程序在很多“意外情况”下都能正确运行,必须做很多工作。这里就不分析具体的程序了,大家可以到网上找来看一下。
文章来源:https://www.codelast.com/
➤➤ 版权声明 ➤➤ 
转载需注明出处:codelast.com 
感谢关注我的微信公众号(微信扫一扫):

wechat qrcode of codelast

《[原创]一维搜索中的划界(Bracket)算法》有3条评论

  1. 楼主写的一系列优化算法非常通俗,调理分明!前段时间一直访问不了楼主的网站,这几天又能访问了!如果能整理成pdf文档那就更好了!

    回复

回复 andy Liu 取消回复