关于Armijo准则和Wolfe准则 | 您所在的位置:网站首页 › 线搜索法的优点 › 关于Armijo准则和Wolfe准则 |
以前一直看不懂Armijo准则和Wolfe准则,直到前段时间看完了Boyd的《凸优化》(王书宁 译),Bilibili上有以这本书为教材的视频教程,是中科大 凌青 老师讲的。 看完后才知道以前对Armijo准则有误解,认为它能在任何函数上使用。其实应用Armijo准则是有前提条件的,要求函数是凸函数且函数定义域是凸集。(就是函数形状像一个“锅”。) Armijo准则用于优化算法中的线搜索子问题。首先任何优化问题都是某个区间(约束)内搜索一个函数的最低点。 《凸优化》里的标准算法是分成三步: 1)先在当前点找一个下降方向dk(梯度下降法用的是负梯度方向,牛顿法用的是牛顿方向) 2)方向确定后再需要确定的是步长alpha_k,这时候由于方向已经确定了,所以相当于用刀在“锅”上沿着dk方向切了一刀,得到一个一维函数。所以这一步就是在这个一维函数上找一个“合适”的步长。这也是线搜索名字的由来。目前线搜索有 精确搜索最优步长方法 和 Armijo准则找次优步长方法。 3)根据方向和步长,更新当前点x(k+1)= x(k) + dk*alpha_k。 Armijo准则和精确搜索最优步长具体哪个更好取决于不同问题。《凸优化》第9章里面有比较,两者迭代次数相差并不大。之所以相差不大,是因为当点x离最优点较远时,x点附近的梯度信息dk其实并不指向最优点“锅底”。dk不准导致alpha_k求得再准也没用。(所以一般情况下用Armijo准则比较多,毕竟它比精确搜索省事)。 ps1:精确步长搜索不准确举例 下图为的f(x1, x2) = x1 * x1 + 4 * x2 * x2的图像: |
CopyRight 2018-2019 实验室设备网 版权所有 |