转载请注明出处:http://www.codelast.com/

line search(一维搜索,或线搜索)是最优化(Optimization)算法中的一个基础步骤/算法。它可以分为精确的一维搜索以及不精确的一维搜索两大类。
在本文中,我想用“人话”解释一下不精确的一维搜索的两大准则:Armijo-Goldstein准则 & Wolfe-Powell准则。
之所以这样说,是因为我读到的所有最优化的书或资料,从来没有一个可以用初学者都能理解的方式来解释这两个准则,它们要么是长篇大论、把一堆数学公式丢给你去琢磨;要么是简短省略、直接略过了解释的步骤就一句话跨越千山万水得出了结论。
每当看到这些书的时候,我脑子里就一个反应:你们就不能写人话吗?

我下面就尝试用通俗的语言来描述一下这两个准则。

【1】为什么要遵循这些准则
由于采用了不精确的一维搜索,所以,为了能让算法收敛(即:求得极小值),人们逐渐发现、证明了一些规律,当你遵循这些规律的时候,算法就很有可能收敛。因此,为了达到让算法收敛的目的,我们就要遵循这些准则。如果你不愿意遵循这些已经公认有效的准则,而是要按自己的准则来设计算法,那么恭喜你,如果你能证明你的做法是有效的,未来若干年后,书本里可能也会出现你的名字。

文章来源:http://www.codelast.com/

【2】Armijo-Goldstein准则
此准则是在196X年的时候由Armijo和Goldstein提出的,当然我没有具体去搜过这俩人是谁。在有的资料里,你可能会看到“Armijo rule”(Armijo准则)的说法,可能是同一回事,不过,任何一个对此作出重要贡献的人都是不可抹杀的,不是么?

Armijo-Goldstein准则的核心思想有两个:①目标函数值应该有足够的下降;②一维搜索的步长α不应该太小。

这两个思想的意图非常明显。由于最优化问题的目的就是寻找极小值,因此,让目标函数函数值“下降”是我们努力的方向,所以①正是想要保证这一点。
同理,②也类似:如果一维搜索的步长α太小了,那么我们的搜索类似于在原地打转,可能也是在浪费时间和精力。

文章来源:http://www.codelast.com/
有了这两个指导思想,我们来看看Armijo-Goldstein准则的数学表达式:

其中, 0 < \rho < \frac{1}{2}
文章来源:http://www.codelast.com/
(1)为什么要规定 \rho \in (0,\frac{1}{2}) 这个条件?其实可以证明:如果没有这个条件的话,将影响算法的超线性收敛性(定义看这个链接,第4条)。在这个速度至关重要的时代,没有超线性收敛怎么活啊!(开个玩笑)
具体的证明过程,大家可以参考袁亚湘写的《最优化理论与方法》一书,我没有仔细看,我觉得对初学者,不用去管它。
(2)第1个不等式的左边式子的泰勒展开式为:
f({x_k} + {\alpha _k}{d_k}) = f({x_k}) + {\alpha _k}{g_k}^T{d_k} + o({\alpha _k})
去掉高阶无穷小,剩下的部分为: f({x_k}) + {\alpha _k}{g_k}^T{d_k}
而第一个不等式右边与之只差一个系数 \rho
我们已知了 {g_k}^T{d_k} < 0 (这是 {d_k} 为下降方向的充要条件),并且 \rho \in (0,\frac{1}{2}) ,因此,1式右边仍然是一个比 f({x_k}) 小的数,即:
f({x_k}) + {\alpha _k}\rho {g_k}^T{d_k} < f({x_k})
也就是说函数值是下降的(下降是最优化的目标)。
文章来源:http://www.codelast.com/
(3)由于 \rho \in (0,\frac{1}{2}){g_k}^T{d_k} < 0{d_k} 是一个下降方向的充要条件),故第2个式子右边比第1个式子右边要小,即:
{\alpha _k}(1 - \rho ){g_k}^T{d_k} < {\alpha _k}\rho {g_k}^T{d_k} < 0
如果步长 \alpha 太小的话,会导致这个不等式接近于不成立的边缘。因此,式2就保证了 \alpha 不能太小。
(4)我还要把很多书中都用来描述Armijo-Goldstein准则的一幅图搬出来说明一下(亲自手绘):

文章来源:http://www.codelast.com/
横坐标是 \alpha ,纵坐标是 f ,表示在 {x_k},{d_k} 均为常量、 \alpha 为自变量变化的情况下,目标函数值随之变化的情况。
之所以说 {x_k},{d_k} 均为常量,是因为在一维搜索中,在某一个确定的点 {x_k} 上,搜索方向 {d_k} 确定后,我们只需要找到一个合适的步长 \alpha 就可以了。
x 为常量, \alpha 为自变量时, f(x + \alpha d) 可能是非线性函数(例如目标函数为 y = {x^2} 时)。因此图中是一条曲线。
右上角的 f({x_k} + \alpha {d_k}) 并不是表示一个特定点的值,而是表示这条曲线是以 \alpha 为自变量、 {x_k},{d_k} 为常量的函数图形。
\alpha = 0 时,函数值为 f({x_k}) ,如图中左上方所示。水平的那条虚线是函数值为 f({x_k}) 的基线,用于与其他函数值对比。
f({x_k}) + {\alpha _k}\rho {g_k}^T{d_k} 那条线在 f({x_k}) 下方(前面已经分析过了,因为 {g_k}^T{d_k} < 0 ), f({x_k}) + {\alpha _k}(1 - \rho ){g_k}^T{d_k} 又在 f({x_k}) + {\alpha _k}\rho {g_k}^T{d_k} 的下方(前面也已经分析过了),所以Armijo-Goldstein准则可能会把极小值点(可接受的区间)判断在区间bc内。显而易见,区间bc是有可能把极小值排除在外的(极小值在区间ed内)。
所以,为了解决这个问题,Wolfe-Powell准则应运而生。
文章来源:http://www.codelast.com/
【3】Wolfe-Powell准则
在某些书中,你会看到“Wolfe conditions”的说法,应该和Wolfe-Powell准则是一回事——可怜的Powell大神又被无情地忽略了...
Wolfe-Powell准则也有两个数学表达式,其中,第一个表达式与Armijo-Goldstein准则的第1个式子相同,第二个表达式为:

这个式子已经不是关于函数值的了,而是关于梯度的。
此式的几何解释为:可接受点处的切线斜率≥初始斜率的 \sigma
上面的图已经标出了 \sigma g_k^T{d_k} 那条线(即 e 点处的切线),而初始点( \alpha = 0 的点)处的切线是比 e 点处的切线要“斜”的,由于 \sigma \in (\rho ,1) ,使得 e 点处的切线变得“不那么斜”了——不知道这种极为通俗而不够严谨的说法,是否有助于你理解。
这样做的结果就是,我们将极小值包含在了可接受的区间内( e 点右边的区间)。
文章来源:http://www.codelast.com/
Wolfe-Powell准则到这里还没有结束!在某些书中,你会看到用另一个所谓的“更强的条件”来代替(3)式,即:

这个式子和(3)式相比,就是左边加了一个绝对值符号,右边换了一下正负号(因为 g_k^T{d_k} < 0 ,所以 - \sigma g_k^T{d_k} > 0 )。
这样做的结果就是:可接受的区间被限制在了 [b,d] 内,如图:

图中红线即为极小值被“夹击”的生动演示。

[原创]用“人话”解释不精确线搜索中的Armijo-Goldstein准则及Wolfe-Powell准则

16 thoughts on “[原创]用“人话”解释不精确线搜索中的Armijo-Goldstein准则及Wolfe-Powell准则

  • 2016 年 12 月 20 日 at 13:30
    Permalink

    g_k^T d_k <0 是d_k为下降方向的充要条件,这个结论能稍微解释一下吗,不太理解,多谢

    Reply
    • 2016 年 12 月 20 日 at 16:54
      Permalink

      可参考这个链接里的第【1】段:http://www.codelast.com/?p=7514

      Reply
  • 2016 年 12 月 07 日 at 14:48
    Permalink

    通俗易懂!不过看官们还要多看看相关代码加深理解。
    个人之见:
    看生涩之文可以俗语述之,可谓大神矣;
    其后可以生涩入理之文述之,可谓小牛矣;
    其后有人引述其生涩之文,可谓大牛矣!

    Reply
    • 2017 年 06 月 28 日 at 19:28
      Permalink

      回头又看了一遍这个文章,发现前面网友说的问题,“可接受的区间被限制在了[b,d]内,如图:”
      感觉应该是[e,d]。不过不影响理解。

      还有一个不好理解的地方,“Goldstein准则可能会把极小值点(可接受的区间)判断在区间bc内。显而易见,区间bc是有可能把极小值排除在外的(极小值在区间ed内)。所以,为了解决这个问题,Wolfe-Powell准则应运而生。”
      个人补充一些不专业的分析以便理解:
      Goldstein准则的第二条可能导致极值点被漏掉,那么需要寻找新搜索温和一些不至于漏掉极小点的alpha新搜索区间(横坐标)下界,以保证Goldstein准则第一条(因为要超线性收敛,这一条不能改)所确定的alpha新搜索区间上界有一个合理的下界,因此提出了Wolfe-Powell准则取代了Goldstein准则的第二条,二者结合在牺牲了一定效率的前提下,保证极小点不被漏掉。

      个人理解,就是Goldstein准则的第一条负责大迈步缩小目标范围上界,Wolfe-Powell准则小步试探别把极小漏掉。

      现在还没有很理解的就是:第一条的大步,为什么不会把极小值漏掉?我还要再理解理解。

      Reply
      • 2017 年 06 月 28 日 at 19:51
        Permalink

        再补充一点:我觉得Goldstein准则的第一条如果rho的值过大,也是有把极小值漏掉可能性的,之前自己调试仿真的时候,确实有完全找不到收敛点,曲线鬼画符一样的现象。
        那么这样说下去,仿真时候,delta和rho的选取,就是rho尽量大(上界尽量小)和delta尽量适中,同时又不能漏掉极小值,以保证精确和效率之间的平衡。
        delta的要适中是因为:斜率所对应的alpha值也就是下界。delta越小,下界减小的越快,对极小值的逼近越精确,书上说这样计算工作量大;delta越大,下界减小的越慢,对极小值的逼近越粗糙也就是弱,书上说这样计算工作量小。这需要在曲线上比划一下斜率的增减。
        为什么delta越小,计算量越大,这个我还没有理解……继续理解理解……

        Reply
  • 2016 年 10 月 08 日 at 23:41
    Permalink

    想问一下 这个准则具体算法怎么做啊。怎么寻找ak。。

    Reply
  • 2016 年 03 月 31 日 at 20:52
    Permalink

    您好,请问如果是求矩阵的话,Armijo准则中,g'd 是一个矩阵不是一个数,怎么办啊。

    Reply
    • 2017 年 05 月 12 日 at 10:07
      Permalink

      请问您这个问题怎么解决的?

      Reply
  • 2015 年 05 月 24 日 at 20:35
    Permalink

    你的 rho 的范围(0,12)是不是有问题啊,谢谢

    Reply
  • 2015 年 03 月 23 日 at 08:53
    Permalink

    可接受点处的切线斜率≥初始斜率的倍
    应该是小于吧,更平缓的点更好!

    Reply
  • 2014 年 11 月 19 日 at 21:09
    Permalink

    感谢,写的真好。
    最后,“可接受的区间被限制在了[b,d]内,如图:”
    是[e,d]吧?

    Reply
  • 2014 年 09 月 12 日 at 11:24
    Permalink

    写得很好,感谢分享!

    Reply
  • 2014 年 03 月 10 日 at 09:13
    Permalink

    楼主对我的帮助很大

    Reply
  • 2013 年 12 月 10 日 at 00:58
    Permalink

    楼主是不是在国科大读研一,我跟你感受差不多,很多大牛教材写的真的不适合初学者,到时老外的书写的图文并茂,通俗易懂,楼主写的很好,通俗易懂,很有共鸣,忘加油,谢谢!

    Reply

发表评论

电子邮件地址不会被公开。 必填项已用*标注