非精确线搜索

Wolfe准则

Wolfe 准则是指: 给定

式中：.

式（2）有时也用另一个更强的条件

来代替. 这样, 当充分小时，可保证式（3)变成近似精确线性搜索。条件（1）和条件（3）也称为强Wolfe准则。

强Wolfe 准则表明, 由该准则得到的新的迭代点的某一邻域内且使目标函数值有一定的下降量.

由于的存在性. 我们有下面的定理.

设 均满足(1) 和(3).

Armijo 准则

Armijo 准则是指: 给定

可以证明, 若, (4) 式成立.

为了程序实现的方便, 我们将Armijo 准则写成下列详细的算法步骤.

算法4（Armijo准则）

步0 给定.

步1 若不等式

成立, 置 停算. 否则, 转步2.

步2 令, 转步1.

下面给出Armijo 准则的Matlab 程序

MATLAB程序

Armijo 搜索规则是许多非线性优化算法都必须执行的步骤, 把它编制成可重复利用的程序模块是很有意义的.

amj.m

function [mk,newxk,newfk]=amj(xk,dk,beta,sigma)
%%Armijo 搜索规则
%input:xk,dk;
%       beta,sigma
%output:mk,xk+1,f(xk+1)

m=0;maxm=20;
while(m<=maxm)
    if(fun(xk+beta^m*dk)<=fun(xk)+sigma*beta^m*gfun(xk)'*dk)
        mk=m;break;
    end
    m=m+1;
end;
alpha=beta^mk;
newxk=xk+alpha*dk;
fk=fun(xk);
newfk=fun(newxk);
%fun为输入函数，gfun为对应梯度函数，均在别处定义

fum.m

function  f = fun(x)
f=100*(x(1)^2-x(2))^2+(x(1)-1)^2;

gfun.m

function gf =gfun(x)
gf=[400*x(1)*(x(1)^2-x(2))+2*(x(1)-1);
    -200*(x(1)^2-x(2))];

实验结果

>> xk=[-1,1]';
>> dk=[1,-2]';
>> beta=0.5;
>> sigma=0.2;
>> [mk,newxk,newfk]=amj(xk,dk,beta,sigma)
mk =
     2
newxk =
                     -0.75
                       0.5
newfk =
                  3.453125