非精确线搜索

Wolfe准则

Wolfe 准则是指: 给定$\rho\in(0,0.5)$,$\sigma\in(\rho,1)$,求$\alpha_k$使得下面两个不等式同时成立:

$$\begin{aligned} &f(\mathbf{x}_k+\alpha_k\mathbf{d}_k)\leq f(\mathbf{x}_k)+\rho\alpha_k\mathbf{g}_k^T\mathbf{d}_k \qquad &(1)\\ &\bigtriangledown f(\mathbf{x}_k+\alpha_k\mathbf{d}_k)^T\mathbf{d}_k\geq\sigma\mathbf{g}_k^T\mathbf{d}_k \qquad &(2) \end{aligned}$$
式中： $\mathbf{g}_k=\mathbf{g}(x_k)=\bigtriangledown f(\mathbf{x}_k)$.

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

$$\left \| \bigtriangledown f(\mathbf{x}_k+\alpha_k\mathbf{d}_k)^T\mathbf{d}_k\right\|\leq-\sigma\mathbf{g}_k^T\mathbf{d}_k \qquad (3)$$
来代替. 这样, 当 $\sigma>0$充分小时，可保证式（3)变成近似精确线性搜索。条件（1）和条件（3）也称为强 Wolfe准则。

强Wolfe 准则表明, 由该准则得到的新的迭代点$\mathbf{x}_{k+1}=\mathbf{x}_k+\alpha_k\mathbf{d}_k$在$\mathbf{x}_k$的某一邻域内且使目标函数值有一定的下降量.

由于$\mathbf{g}_k^T\mathbf{d}_k<0$,可以证明Wolfe 准则的有限终止性, 即步长$\alpha_k$的存在性. 我们有下面的定理.

设$f(\mathbf{x})$有下界且$\mathbf{g}_k^T\mathbf{d}_k<0$, 令$\rho\in(0,0.5)$,$\sigma\in(\rho,1)$. 则存在一个区间$[a,b](0<a<b)$, 使每个$\alpha\in[a,b]$均满足(1) 和(3).

Armijo 准则

Armijo 准则是指: 给定$\beta\in(0,1)$,$\sigma\in(0,0.5)$. 令步长因子$\alpha_k=\beta^{m_k}$,其中$m_k$是满足下列不等式的最小非负整数:

$$f(\mathbf{x}_k+\beta^m\mathbf{d}_k)\leq f(\mathbf{x}_k)+\sigma\beta^m\mathbf{g}_k^T\mathbf{d}_k \qquad (4)$$
可以证明, 若 $f(\mathbf{x})$是连续可微的且满足 $\mathbf{g}_k^T\mathbf{d}_k<0$, 则 Armijo 准则是有限终止的, 即存在正数 $\sigma$, 使得对于充分大的正整数 $m$, (4) 式成立.

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

算法4（Armijo准则）

步0 给定$\beta\in(0,1)$, $\sigma\in(0,0.5)$. 令 $m=0$.

步1 若不等式

$$f(\mathbf{x}_k+\beta^m\mathbf{d}_k)\leq f(\mathbf{x}_k)+\sigma\beta^m\mathbf{g}_k^T\mathbf{d}_k$$
成立, 置 $m_k=m,\mathbf{x}_{k+1}=\mathbf{x}_k+\beta^{m_k}\mathbf{d}_k$停算. 否则, 转步2.

步2 令$m=m+1$, 转步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