优化方法基础系列-非精确的一维搜索技术

作者: oskor | 来源:发表于2019-02-27 20:55 被阅读0次

优化方法基础系列-非精确的一维搜索技术
优化方法基础系列-精确的一维搜索技术
搜索引擎系统原理剖析
高级SEO关键词优化企业SEO推广技术SEO优化网站关键词排名
一维搜索
图像分类实践及其优化
Google如何使用高级搜索？
2018-12-05 seo基础总结
优化方法基础系列-优化问题分类
SEO高级优化技巧

选择最优步长的精确搜索方法往往计算量大，特别是当迭代点远离最优解时，效率很低，而且很多最优化算法的收敛速度并不依赖于精确的一维搜索过程。这促使一些研究者放宽了一维搜索的精确要求，而去保证目标函数在每次迭代有满意的下降量，这类方法称为非精确的一维搜索方法或可接受的一维搜索方法，它可以大大节省计算量。

不精确的一维搜索方法核心问题是选取可接受的步长 $\lambda_k$ 使得 $f(\boldsymbol x_k)-f(\boldsymbol x_k+\lambda_k\boldsymbol d_k)$ 得到一个满意的水平，即足够的下降且大范围收敛。因此，研究者提出了一些准则，以满足不精确搜索能也能收敛的条件。Armijo-Goldstein和Wolf-Powell准则为非精确一维搜索的两大准则。

Armijo-Goldstein准则

Armijo-Goldstein准则核心思想就两点：

1、目标函数值应该有足够的下降
2、一维搜索的步长 $\lambda$ 不应该太小

这两点意图是非常明显，由于最优化问题就是寻找极小值，所以使得目标函数值下降，是我们努力的方向，此外如果搜索步长太小，可能原地打转，影响收敛速度。具体方法如下：

假设 $\boldsymbol d_k$ 是一个下降方向，记 $\boldsymbol{g}_k=\nabla f(\boldsymbol{x}_k)$ ，有：

$f(\boldsymbol{x}_k+\lambda\boldsymbol{d}_k)=f(\boldsymbol{x}_k)+\lambda\nabla f(\boldsymbol{x}_k)^T\boldsymbol{d}_k+O(||\lambda\boldsymbol{d}_k||)$

则 $\boldsymbol{g}_k^T\boldsymbol{d}_k<0,f(\boldsymbol{x}_k)-f(\boldsymbol{x}_k+\lambda\boldsymbol{d}_k)$ 的一个合理的下界（保证下降）：

$f(\boldsymbol{x}_k)-f(\boldsymbol{x}_k+\lambda\boldsymbol{d}_k)\geq -\rho \lambda\boldsymbol{g}_k^T\boldsymbol{d}_k,\rho \in (0,0.5)$

再给其一个上界限制（ $\lambda$ 不能太小）:

$f(\boldsymbol{x}_k)-f(\boldsymbol{x}_k+\lambda\boldsymbol{d}_k)\leq -(1-\rho) \lambda\boldsymbol{g}_k^T\boldsymbol{d}_k,\rho \in (0,0.5)$

那么Armijo-Goldstein准则可描述为：

可接受的 $\lambda$ 应该满足：

$f(\boldsymbol{x}_k)+(1-\rho) \lambda\boldsymbol{g}_k^T\boldsymbol{d}_k\leq f(\boldsymbol{x}_k+\lambda\boldsymbol{d}_k)\leq f(\boldsymbol{x}_k)+\rho\lambda\boldsymbol{g}_k^T\boldsymbol{d}_k,\rho \in (0,0.5)$

注：如果 $\rho$ 不在这个范围内，将影响其超线性收敛性。

图1 Armijo-Goldstein准则示例

令 $\varphi (\lambda) = f(\boldsymbol{x}_k+\lambda\boldsymbol{d}_k)$ ，即固定 $\boldsymbol{x}_k$ 和方向 $\boldsymbol{d}_k$ ，求解满足条件的步长，则Armijo-Goldstein可写为：

$\varphi (0)+(1-\rho)\lambda\varphi ^\prime(0)\leq \varphi(\lambda)\leq \varphi(0)+\rho\lambda\varphi^\prime(0)$

从上图和公式中，可以看出 $\varphi(0)+\rho\lambda\varphi^\prime(0)$ 在 $\varphi(0)$ 的下方， $\varphi(0)+(1-\rho)\lambda\varphi^\prime(0)$ 在 $\varphi(0)+\rho\lambda\varphi^\prime(0)$ 的下方，所以 $[b,c]$ 区间都是在满足条件的步长。然而，Armijo-Goldstein准则可能会把极值点判断在可接受的范围之外，所以为了解决这一问题，Wolf-Powell准则应用而生。

图 2 Armijo-Goldstein 准则流程图

Algorithm 9 Armijo-Goldstein准则

function lamda = ArmijoGoldstein(func,gfunc,lamda0,ro,apha,iterNum,plotFlag)
if nargin<7
    plotFlag = 1;
end
if nargin<6
    iterNum = 100;
end
if nargin<5
    apha = 2;
end
if nargin<4
    ro = 0.1;
end
if nargin<3
    lamda0 = 1;
end

a = 0;
b = inf;
lamda =lamda0;
f0 = func(0);
g0 = gfunc(0);
if plotFlag == 1
    figH = figure();
end

while iterNum
    flamda = func(lamda);
    if plotFlag == 1       
        pause(1)
        plot(0:0.01:4,func(0:0.01:4),'-b');
        hold on;
        plot([0,4],[f0,f0],'-y');
        plot([0,4],[f0,f0+ro*4*g0],'-or');
        plot([0,4],[f0,f0+(1-ro)*4*g0],'-og');
        plot([0,lamda],[f0,flamda],'-*k');
        plot(a,func(a),'-*g');
        if ~isinf(b)
            plot(b,func(b),'-*r');
        end
        hold off;
    end
    if flamda<=f0+ro*lamda*g0 %满足Armijo准则，足够的下降
        if flamda>=f0+(1-ro)*lamda*g0 %满足Goldstein,步长不会太小
            break;
        else %不满足Goldstein，步长太小，左端的a设置为lamda
            a = lamda;
            if isinf(b)%右端的b为空的时候，说明Armijo准则一直是满足的，步长太小了，扩大步长
                lamda = apha*lamda;
            else
                lamda = (a+b)/2; %步长设定为区间的中值
            end
        end
    else%下降不足，缩小b和步长
        b = lamda;
        lamda = (a+b)/2;
    end
    iterNum = iterNum - 1;
end

%示例
%lamda = ArmijoGoldstein(@(x)(sin(-4+x)-1),@(x)(cos(-4+x)),1,0.4,2,100,1)

Wolf-Powell 准则

Wolf-Powell准则下界和Armijo-Goldstein准则是一样的，即：

$f(\boldsymbol{x}_k+\lambda\boldsymbol{d}_k)\leq f(\boldsymbol{x}_k)+\rho\lambda\boldsymbol{g}_k^T\boldsymbol{d}_k,\rho \in (0,0.5)$

为了保证足够的步长以及可接受的区间包含极小值点，上界被定义:

$\boldsymbol{g}_{k+1}^T\boldsymbol{d}_k\geq\sigma \boldsymbol{g}_k^T\boldsymbol{d}_k,\sigma \in (\rho,1)$

也就是：

$\varphi ^\prime(\lambda)\geq \sigma \varphi^\prime(0)$

其说明在点 $\lambda$ 处的斜率应该大于起始点斜率的 $\sigma$ 倍。 $\varphi^\prime(0)$ 是负值，所以上界的含义就是可接受的范围中斜率应该是接近零的负值或者正值。

此外，还有一种更为严苛的准则，称为强Wolf调节，即：

$\vert \varphi^\prime(\lambda) \vert \leq -\sigma \varphi^\prime(0)$

强Wolf条件使得可接受的范围的斜率的正值不至于过大，可以将远离极小值点的步长排除在外。一般 $\sigma$ 越小，线性搜索越精确，不过 $\sigma$ 越小，工作量越大，一般取 $\rho = 0.1, \sigma\in [0.6,0.8]$

图 3 强Wolf条件示意图

Algorithm 10 Wolf-Powell 准则

function lamda = WolfPowell(func,gfunc,lamda0,ro,sigma,apha,iterNum,plotFlag)
if nargin<8
    plotFlag = 1;
end
if nargin<7
    iterNum = 100;
end
if nargin<6
    apha = 2;
end
if nargin<5
    ro = 0.1;
end
if nargin<4
    sigma = 0.7;
end
if nargin<3
    lamda0 = 1;
end

a = 0;
b = inf;
lamda =lamda0;
f0 = func(0);
g0 = gfunc(0);
if plotFlag == 1
    figH = figure();
    for i=0:0.01:4
        if gfunc(i)>=sigma*g0;
            gs_i = i;
            break;
        end
    end
end

while iterNum
    flamda = func(lamda);
    if plotFlag == 1       
        pause(1)
        plot(0:0.01:4,func(0:0.01:4),'-b');
        hold on;
        plot([0,4],[f0,f0],'-y');
        plot([0,4],[f0,f0+ro*4*g0],'-or');
        plot([gs_i-0.5,gs_i+0.5],[func(gs_i)+(-0.5)*sigma*g0,func(gs_i)+(0.5)*sigma*g0],'-og');
        plot([0,lamda],[f0,flamda],'-*k');
        plot(a,func(a),'-*g');
        if ~isinf(b)
            plot(b,func(b),'-*r');
        end
        hold off;
    end
    if flamda<=f0+ro*lamda*g0 %满足Armijo准则，足够的下降
        if gfunc(lamda)>=sigma*g0 %满足wolf-powell,步长不会太小
            break;
        else %不满足wolf-powell，步长太小，左端的a设置为lamda
            a = lamda;
            if isinf(b)%右端的b为空的时候，说明Armijo准则一直是满足的，步长太小了，扩大步长
                lamda = apha*lamda;
            else
                lamda = (a+b)/2; %步长设定为区间的中值
            end
        end
    else%下降不足，缩小b和步长
        b = lamda;
        lamda = (a+b)/2;
    end
    iterNum = iterNum - 1;
end

%example
%lamda = WolfPowell(@(x)(sin(-4+x)-1),@(x)(cos(-4+x)),1,0.4,0.45,2,100,1)

图4 Wolf-Powell条件示意图

后退法（简单准则）

后退法仅采用了Armijo-Goldstein准则的下界限制，即保证函数的下降，此外要求 $\lambda$ 不要太小即可。其基本思想是：

给定 $\rho \in (0,0.5),0<l<u<1$
Step1 令 $\lambda=1$
Step2 如果 $f(\boldsymbol{x}_k+\lambda\boldsymbol{d}_k)\leq f(\boldsymbol{x}_k)+\rho\lambda\boldsymbol{g}_k^T\boldsymbol{d}_k$ ，则令 $\lambda_k=\lambda$ 停止迭代，输出 $\lambda_k$ ;否则转Step3
Step3 $\lambda:=\omega \lambda,\omega\in[l,u]$ ,转Step2

关于这些准则的有效性，比如步长的存在性，大范围收敛性质可参阅刘红英版本的数值规划基础或者Numerical Optimization。后来学者们又发展了Curry-Altman步长律、Danilin-Pshenichuyi步长律、De Leone-Grippo步长律等，这些步长律或者准则会在后文的具体优化算法中有所涉及，使用的过程中可能会大大加速优化方法的收敛。

参考文献：

[1] Numerical Optimization. Jorge Nocedal

优化方法基础系列-非精确的一维搜索技术
选择最优步长的精确搜索方法往往计算量大，特别是当迭代点远离最优解时，效率很低，而且很多最优化算法的收敛速度并不依赖...
优化方法基础系列-精确的一维搜索技术
在学习各种优化方法之前，我们需要先从简单的一维优化问题开始，即只有单一变量的优化问题，解决这类问题的方法可称为一维...
搜索引擎系统原理剖析
目录【1】搜索引擎概述【2】搜索引擎的基础技术【3】搜索引擎的平台基础【4】搜索结果的改善优化【1】搜索...
高级SEO关键词优化企业SEO推广技术SEO优化网站关键词排名
高级SEO关键词优化企业SEO推广技术SEO优化网站关键词排名搜索引擎优化百度自然搜索基础视频教程在互联网营销...
一维搜索
一维搜索的分类精确一维搜索：1)区间收缩法；2)函数逼近法；非精确一维搜索：1)Armijo准则；2)Wol...
图像分类实践及其优化
一、基础网络二、网络优化相关技术 1、层合并/池化技术一种流行的CNN优化技术是池化。池化是一种用智能方法减少...
Google如何使用高级搜索？
优化网页搜索您可以在搜索时使用符号或字词，以便让搜索结果更加精确。 Google 搜索通常会忽略不属于搜索运算符...
2018-12-05 seo基础总结
seo基础、优缺点什么是seo 搜索引擎优化广告位下的自然排名 SEO是指从自然搜索结果获得网站流量的技术和过...
优化方法基础系列-优化问题分类
最优化问题可以按照优化问题的状态来进行分类，可分了两类，即静态问题和动态问题。本优化方法系列主要从静脉问题方面进行...
SEO高级优化技巧
SEO高级优化技巧基础优化更多的是关于技术方面的...