選擇最優(yōu)步長的精確搜索方法往往計(jì)算量大池充，特別是當(dāng)?shù)c(diǎn)遠(yuǎn)離最優(yōu)解時(shí)夹纫，效率很低，而且很多最優(yōu)化算法的收斂速度并不依賴于精確的一維搜索過程。這促使一些研究者放寬了一維搜索的精確要求任岸，而去保證目標(biāo)函數(shù)在每次迭代有滿意的下降量剑按，這類方法稱為非精確的一維搜索方法或可接受的一維搜索方法，它可以大大節(jié)省計(jì)算量猜敢。

不精確的一維搜索方法核心問題是選取可接受的步長 $\lambda_k$ 使得 $f(\boldsymbol x_k)-f(\boldsymbol x_k+\lambda_k\boldsymbol d_k)$ 得到一個(gè)滿意的水平，即足夠的下降且大范圍收斂。因此净赴，研究者提出了一些準(zhǔn)則珍特，以滿足不精確搜索能也能收斂的條件。Armijo-Goldstein和Wolf-Powell準(zhǔn)則為非精確一維搜索的兩大準(zhǔn)則魔吐。

Armijo-Goldstein準(zhǔn)則

Armijo-Goldstein準(zhǔn)則核心思想就兩點(diǎn)：

1扎筒、目標(biāo)函數(shù)值應(yīng)該有足夠的下降
2、一維搜索的步長 $\lambda$ 不應(yīng)該太小

這兩點(diǎn)意圖是非常明顯酬姆，由于最優(yōu)化問題就是尋找極小值嗜桌，所以使得目標(biāo)函數(shù)值下降，是我們努力的方向辞色，此外如果搜索步長太小骨宠，可能原地打轉(zhuǎn)，影響收斂速度相满。具體方法如下：

假設(shè) $\boldsymbol d_k$ 是一個(gè)下降方向层亿，記 $\boldsymbol{g}_k=\nabla f(\boldsymbol{x}_k)$ ，有：

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

則 $\boldsymbol{g}_k^T\boldsymbol2uiimzf_k<0,f(\boldsymbol{x}_k)-f(\boldsymbol{x}_k+\lambda\boldsymbolspzozua_k)$ 的一個(gè)合理的下界（保證下降）：

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

再給其一個(gè)上界限制（ $\lambda$ 不能太辛⒚馈）:

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

那么Armijo-Goldstein準(zhǔn)則可描述為：

可接受的 $\lambda$ 應(yīng)該滿足：

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

注：如果 $\rho$ 不在這個(gè)范圍內(nèi)匿又，將影響其超線性收斂性。

圖1 Armijo-Goldstein準(zhǔn)則示例

令 $\varphi (\lambda) = f(\boldsymbol{x}_k+\lambda\boldsymbolwoshsuw_k)$ 建蹄，即固定 $\boldsymbol{x}_k$ 和方向 $\boldsymbolmt8ld33_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]$ 區(qū)間都是在滿足條件的步長劲腿。然而旭绒，Armijo-Goldstein準(zhǔn)則可能會把極值點(diǎn)判斷在可接受的范圍之外，所以為了解決這一問題焦人，Wolf-Powell準(zhǔn)則應(yīng)用而生挥吵。

圖 2 Armijo-Goldstein 準(zhǔn)則流程圖

Algorithm 9 Armijo-Goldstein準(zhǔn)則

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準(zhǔn)則，足夠的下降
        if flamda>=f0+(1-ro)*lamda*g0 %滿足Goldstein,步長不會太小
            break;
        else %不滿足Goldstein垃瞧，步長太小蔫劣，左端的a設(shè)置為lamda
            a = lamda;
            if isinf(b)%右端的b為空的時(shí)候坪郭，說明Armijo準(zhǔn)則一直是滿足的个从，步長太小了，擴(kuò)大步長
                lamda = apha*lamda;
            else
                lamda = (a+b)/2; %步長設(shè)定為區(qū)間的中值
            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 準(zhǔn)則

Wolf-Powell準(zhǔn)則下界和Armijo-Goldstein準(zhǔn)則是一樣的嗦锐，即：

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

為了保證足夠的步長以及可接受的區(qū)間包含極小值點(diǎn)嫌松，上界被定義:

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

也就是：

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

其說明在點(diǎn) $\lambda$ 處的斜率應(yīng)該大于起始點(diǎn)斜率的 $\sigma$ 倍。 $\varphi^\prime(0)$ 是負(fù)值奕污，所以上界的含義就是可接受的范圍中斜率應(yīng)該是接近零的負(fù)值或者正值萎羔。

此外，還有一種更為嚴(yán)苛的準(zhǔn)則碳默，稱為強(qiáng)Wolf調(diào)節(jié)贾陷，即：

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

強(qiáng)Wolf條件使得可接受的范圍的斜率的正值不至于過大，可以將遠(yuǎn)離極小值點(diǎn)的步長排除在外嘱根。一般 $\sigma$ 越小髓废，線性搜索越精確，不過 $\sigma$ 越小该抒，工作量越大慌洪，一般取 $\rho = 0.1, \sigma\in [0.6,0.8]$

圖 3 強(qiáng)Wolf條件示意圖

Algorithm 10 Wolf-Powell 準(zhǔn)則

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準(zhǔn)則，足夠的下降
        if gfunc(lamda)>=sigma*g0 %滿足wolf-powell,步長不會太小
            break;
        else %不滿足wolf-powell凑保，步長太小冈爹，左端的a設(shè)置為lamda
            a = lamda;
            if isinf(b)%右端的b為空的時(shí)候，說明Armijo準(zhǔn)則一直是滿足的欧引，步長太小了频伤，擴(kuò)大步長
                lamda = apha*lamda;
            else
                lamda = (a+b)/2; %步長設(shè)定為區(qū)間的中值
            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條件示意圖

后退法（簡單準(zhǔn)則）

后退法僅采用了Armijo-Goldstein準(zhǔn)則的下界限制芝此，即保證函數(shù)的下降剂买，此外要求 $\lambda$ 不要太小即可。其基本思想是：

給定 $\rho \in (0,0.5),0<l<u<1$
Step1 令 $\lambda=1$
Step2 如果 $f(\boldsymbol{x}_k+\lambda\boldsymbol2odwlct_k)\leq f(\boldsymbol{x}_k)+\rho\lambda\boldsymbol{g}_k^T\boldsymbolgoswri8_k$ 癌蓖，則令 $\lambda_k=\lambda$ 停止迭代瞬哼，輸出 $\lambda_k$ ;否則轉(zhuǎn)Step3
Step3 $\lambda:=\omega \lambda,\omega\in[l,u]$ ,轉(zhuǎn)Step2

關(guān)于這些準(zhǔn)則的有效性，比如步長的存在性租副，大范圍收斂性質(zhì)可參閱劉紅英版本的數(shù)值規(guī)劃基礎(chǔ)或者Numerical Optimization坐慰。后來學(xué)者們又發(fā)展了Curry-Altman步長律、Danilin-Pshenichuyi步長律用僧、De Leone-Grippo步長律等结胀，這些步長律或者準(zhǔn)則會在后文的具體優(yōu)化算法中有所涉及，使用的過程中可能會大大加速優(yōu)化方法的收斂责循。

參考文獻(xiàn)：

[1] Numerical Optimization. Jorge Nocedal

優(yōu)化方法基礎(chǔ)系列-非精確的一維搜索技術(shù)

優(yōu)化方法基礎(chǔ)系列-非精確的一維搜索技術(shù)

Armijo-Goldstein準(zhǔn)則

Wolf-Powell 準(zhǔn)則

后退法（簡單準(zhǔn)則）