Armijo-Goldstein准则
此准则是在196X年的时候由Armijo和Goldstein提出的,当然我没有具体去搜过这俩人是谁。在有的资料里,你可能会看到“Armijo rule”(Armijo准则)的说法,可能是同一回事,不过,任何一个对此作出重要贡献的人都是不可抹杀的,不是么?
Armijo-Goldstein准则的核心思想有两个:①目标函数值应该有足够的下降;②一维搜索的步长α不应该太小。
这两个思想的意图非常明显。由于最优化问题的目的就是寻找极小值,因此,让目标函数函数值“下降”是我们努力的方向,所以①正是想要保证这一点。
同理,②也类似:如果一维搜索的步长α太小了,那么我们的搜索类似于在原地打转,可能也是在浪费时间和精力。
(1)为什么要规定这个条件?其实可以证明:如果没有这个条件的话,将影响算法的超线性收敛性。在这个速度至关重要的时代,没有超线性收敛怎么活啊!
具体的证明过程,大家可以参考袁亚湘写的《最优化理论与方法》一书,我没有仔细看,我觉得对初学者,不用去管它。
(2)第1个不等式的左边式子的泰勒展开式为:
去掉高阶无穷小,剩下的部分为:
而第一个不等式右边与之只差一个系数
我们已知了(这是为下降方向的充要条件),并且,因此,1式右边仍然是一个比小的数,即:
也就是说函数值是下降的(下降是最优化的目标)。
%Armijo条件是一种一维搜索的停止条件。
%不精确的一维搜索条件规定αk首先应该保证使目标函数充分减小,这个条件使用以下不等式描述:
%f (xk+αpk)≤f(xk )+c1α△fTpk
%其中c1∈(0,1)的常数。也就是说,目标函数f的下降要与步长和下降方向成一定的比例。
%c1是一个很小的值,一般选择c1=10-4。
function mk = armijo( fun, xk, rho, sigma, gk ) %确定armijo步长
assert( rho > 0 && rho < 1 ); #停止判断条件
assert( sigma > 0 && sigma < 0.5 ); %停止判断条件
mk = 0; max_mk = 100; %设定初始值
while mk <= max_mk %循环
x = xk - rho^mk * gk; %armijo步长
if feval( fun, x ) <= feval( fun, xk ) - sigma * rho^mk * norm( gk )^2 %判断循环跳出
break;
end
mk = mk + 1; %下一层循环
end
return; %返回步长