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

在學(xué)習(xí)各種優(yōu)化方法之前朵诫，我們需要先從簡(jiǎn)單的一維優(yōu)化問(wèn)題開(kāi)始哼审，即只有單一變量的優(yōu)化問(wèn)題禁谦，解決這類問(wèn)題的方法可稱為一維搜索技術(shù)绝编，亦可稱為線性所搜（Line Search）僻澎。一維搜索技術(shù)既可以獨(dú)立的應(yīng)用于求解單變量的優(yōu)化問(wèn)題，同時(shí)又是求解多變量?jī)?yōu)化問(wèn)題的常用手段十饥。

在大多數(shù)多變量函數(shù)的最優(yōu)化中窟勃，迭代格式為：

\boldsymbol{x}_{k+1}=\boldsymbol{x}_{k}+\alpha_{k}\boldsymbolyqsumoo_{k}
其中最為關(guān)鍵的就是往哪走的搜索方向\boldsymbolqq64gwy_k和走多少的步長(zhǎng)因子\alpha_k,如果確定了搜索方向，那么求解步長(zhǎng)因子\alpha_k的問(wèn)題就是一維優(yōu)化問(wèn)題逗堵，不妨設(shè)：

\varphi(\alpha ) = f(\boldsymbol{x}_{k}+\alpha\boldsymbolccgiyuu_k)
這樣凡從\boldsymbol{x}_k出發(fā)秉氧，沿搜索方向\boldsymboli6ieu4u_k,確定步長(zhǎng)因子\alpha_k,使得\varphi(\alpha)<\varphi(0)(該系列文章涉及的優(yōu)化方法以及步驟均默認(rèn)為求極小值)的問(wèn)題就是關(guān)于步長(zhǎng)因子\alpha的一維搜索問(wèn)題。其主要結(jié)構(gòu)可作如下概括：首先確定包含問(wèn)題最優(yōu)解的搜索區(qū)間蜒秤，然后采用某種分割技術(shù)或者插值方法縮小這個(gè)區(qū)間汁咏，進(jìn)行搜索求解。

一維搜索方法可以分為兩大類作媚，即精確搜索和非精確搜索攘滩。精確搜索，顧名思義就是求\varphi(\alpha)的極小值纸泡，此時(shí)得到的\alpha_k稱為最優(yōu)步長(zhǎng)因子漂问。如果選取的\alpha_k使得\varphi(\alpha_k)<\varphi (0)在可接受的范圍內(nèi)，這種情況就稱為非精確的搜索女揭。由于實(shí)際計(jì)算中蚤假，一般做不到精確的一維搜索，實(shí)際上也沒(méi)有必要做到這一點(diǎn)田绑，因?yàn)榫_的一維搜索需要付出較高的代價(jià)勤哗，對(duì)加速收斂作用不大，因此花費(fèi)計(jì)算量較少的不精確的一維搜索技術(shù)方法受到更為廣泛的重視和歡迎掩驱。 但了解精確的一維搜索技術(shù)對(duì)于非精確的技術(shù)有幫助芒划，所以本系列最開(kāi)始依然先從精確的一維搜索技術(shù)展開(kāi)。

精確的一維搜索技術(shù)

通常根據(jù)算法中有無(wú)使用導(dǎo)數(shù)欧穴，將精確的一維搜索技術(shù)分為兩類民逼，即無(wú)導(dǎo)數(shù)信息的試探法，包括二分法涮帘、黃金分割法拼苍、Fibonacci法、進(jìn)退法等；有導(dǎo)數(shù)信息的插值法疮鲫，包含二次插值法吆你、牛頓法等。

高低高(單峰)區(qū)間定位(initially bracketing a minmum)

對(duì)于求根問(wèn)題俊犯，通過(guò)兩點(diǎn)相乘為負(fù)即可確定一個(gè)區(qū)間（連續(xù)函數(shù)）妇多。那么對(duì)于求解一維函數(shù)f(x)的局部極小值得問(wèn)題，可以通過(guò)三點(diǎn)信息獲得（a triplet of points）燕侠，即如果a<x_1<b者祖，使得f(x_1)均小于f(a)和f(b)，且函數(shù)連續(xù)绢彤，那[a,b]之間就存在一個(gè)局部極小值七问，如下圖所示：

圖 1 高低高區(qū)間示意圖

高低高區(qū)間的確定，最為常見(jiàn)的方法是進(jìn)退法茫舶。

進(jìn)退法的思想是先試探械巡、再判斷是進(jìn)還是退，直到得到a<x_1<b饶氏，且f(x_1)均小于f(a)和f(b)情況坟比，則可確定區(qū)間。

Algorithm 1 進(jìn)退法

function [a,b,c] = bracketAdvanceBack(func,x0,h0,plotFlag)
if nargin < 4
    plotFlag = 0;
end
if nargin <3
    h0 = 0.01;
end
if nargin <2
    x0 = 0;
end

if plotFlag == 1
    figH = figure();
    k = 0;
end

x1 = x0;
h = h0;
x2 = x1 + h;
fx1 = func(x1);
fx2 = func(x2);
%試探
if fx2>=fx1 %說(shuō)明極小點(diǎn)位于x1的左方嚷往，后退搜索,即將步長(zhǎng)設(shè)定 為負(fù)葛账，x1和x2交換
    h = -h0;
    swap(x1,x2);
    swap(fx1,fx2);
end
at = x0;
bt = x2;
iterNum = 1000;

while(iterNum)
    h = 2*h;
    x3 = x2 + h;
    fx3 = func(x3);
    ct = x3;
    if plotFlag == 1
       % pause(1);
        plot(x0-300*h0:h0:x0+300*h0,func(x0-300*h0:h0:x0+300*h0),'-b',x1...
,func(x1),'or',x2,func(x2),'og',x3,func(x3),'ob');
        print(figH,'-dpng',strcat('plotIm_',num2str(k)));
        k = k+1;
    end
    if fx3>fx2
        at = x1;
        bt = x2;
        ct = x3;
        break;
    else
        x1 = x2;
        x2 = x3;
        fx2 = fx3;
    end
    iterNum = iterNum - 1;
end

a = min(at,ct);
b = bt;
c = max(at,ct);

end

function [x,y]=swap(x,y)
t = x;
x = y;
y = t;
end

注：本系列相關(guān)matlab代碼，對(duì)輸入的部分異常情況沒(méi)有進(jìn)行處理

Numerical recipes 10.1節(jié)中提供一種利用三點(diǎn)構(gòu)建的拋物線極小點(diǎn)進(jìn)行高低高區(qū)間的搜索皮仁，這種方法相比傳統(tǒng)的進(jìn)退法在同樣的初始條件下籍琳，能更快的找到高低高區(qū)間，算法如下：

Algorithm 2 拋物線法

function [a,b,c] = bracket(func,a,b,plotFlag,step,steplimit)
if nargin < 6
    steplimit = 10;
end

if nargin < 5
    step = 1.618034;
end

if nargin < 4
    plotFlag = 0;
end
if nargin <3
    b= 1;
end

if nargin <2
   a = 0;
end

if abs(a-b) > 1
    warning('the initial interval is too lager and the result may be unsatisfactory!')
end

if a>b
    [a,b]=swap(a,b);
end
abInt = (b-a)/10;
abInt = min(abInt,0.1);

GOLD = step;
GLIMIT = steplimit;

ax = a;
bx = b;

fax = func(ax);
fbx = func(bx);

if fbx>fax
    [fbx,fax]=swap(fbx,fax);
    [bx,ax]=swap(bx,ax);
    abInt = -abInt;
end

cx = bx + GOLD*(bx-ax);
fcx = func(cx);

if plotFlag == 1   
    figure, plot(ax:abInt:cx,func(ax:abInt:cx),'-b',ax,func(ax),'or',bx,func(bx),'og',cx,func(cx),'ob');
end

while fbx>fcx
    r = (bx-ax)*(fbx-fcx);
    q = (bx-cx)*(fbx-fax);
    ux = bx -((bx-cx)*q-(bx-ax)*r)/(2.0*MySignFunc(max(abs(q-r),eps),q-r));%三點(diǎn)構(gòu)建拋物線的極值點(diǎn);
    uxlim = bx + GLIMIT*(cx-bx);
    
    if (bx-ux)*(ux-cx) > 0 %如果u在bx和cx之間
        fux = func(ux);
        if fux<fcx %我們就得到了一個(gè)高低高區(qū)間 在 bx ux cx
            ax = bx;
            bx = ux;
            %cx = cx;
            break;
        else if fux>fbx %我們就得到一個(gè)高低高區(qū)間 在 ax bx ux
                %ax = ax;
                %bx = bx;
                cx = ux;
                break;
            end
        end
        ux = cx + GOLD*(cx-bx); %如果上面兩個(gè)情況都不滿足贷祈，就在cx的基礎(chǔ)上擴(kuò)大 ux
    elseif (cx-ux)*(ux-uxlim)>0 %如果ux在cx和uxlim之間
        fux = func(ux);
        if fux<fcx %fux是小于fcx的趋急，說(shuō)明 這個(gè)時(shí)候還有擴(kuò)大的空間 ax cx ux
            bx = cx;
            cx = ux;
            ux = ux + GOLD*(ux-bx);%ux-cx
        end
    elseif (ux-uxlim)*(uxlim-cx)>=0.0 %如果uxlim在ux 和 cx 之間
        ux = uxlim;
    else
        ux = ux + GOLD*(cx-bx);
    end
    
    ax = bx;
    bx = cx;
    cx = ux;
    fax = func(ax);
    fbx = func(bx);
    fcx = func(cx);
    
    if plotFlag == 1   
        pause(1);
        plot(ax:abInt:cx,func(ax:abInt:cx),'-b',ax,func(ax),'or',bx,func(bx),'og',cx,func(cx),'ob');
    end
    
end

abc = sort([ax,bx,cx]);
a = abc(1);
b = abc(2);
c = abc(3);

end

function [x,y]=swap(x,y)
t = x;
x = y;
y = t;
end

function a = MySignFunc(a,x)
a = abs(a);
if x<0
    a = -a;
end
end

二分法

嚴(yán)苛點(diǎn)，假設(shè)函數(shù)在[a,b]區(qū)間存在極小值势誊，且x_1<x_2,x_1,x_2\in[a,b]
（1）若f(x_1)>f(x_2)呜达，則\forall x\in [a,x_1],f(x)>f(x_2),說(shuō)明極小值在[x_1,b];
（2）若f(x_1)\leq f(x_2)，則\forall x\in [x_2,b],f(x)\geq f(x_1),說(shuō)明極小值在[a,x_2];
則稱為f(x)在[a,b]區(qū)間上是單谷函數(shù)粟耻。在搜索區(qū)間時(shí)查近，我們找到的高低高區(qū)間往往是單谷函數(shù)，確保單谷函數(shù)后挤忙，就有一系列的分割式的方法進(jìn)行精確的一維搜索極值的方法霜威，其中最簡(jiǎn)單就是二分法，類似求函數(shù)過(guò)零點(diǎn)的方法册烈，具體如下：

Algorithm 3 二分法

function x_min = BiSection(func,a,b,c,toll,plotFlag)
if nargin < 6
    plotFlag = 0;
end

if nargin < 5
    toll = 10^(-8);
end

if (a-b)*(b-c)<=0
    x_min = 0;
    disp('a<b<c or a>b>c is needed!');
    return ;
end

if (a>c)
    t=a;
    a=c;
    c=t;
end

x_mid = (a+c)/2;

if plotFlag == 1
    figH = figure();
    acInt = (c-a)/100;
    plot(a:acInt:c,func(a:acInt:c),'-b',x_mid,func(x_mid),'-ro',a,func(a),'-*r',b,...
    func(b),'-*g',c,func(c),'-*b');
    hold on;
end

while abs(a-c)>2*toll
    
    if x_mid == b
        x_mid = (a+b)/2;
    end
    
    if x_mid>b
        if func(x_mid) > func(b) %極小值在b的右端
            c = x_mid;
        else %極小值在x_mid的左端
            a = b;
            b = x_mid;
        end
    else
        if func(x_mid) > func(b) %極小值在b的右端
            a = x_mid;
        else %極小值在x_mid的左端
            c = b;
            b = x_mid;
        end
    end
    x_mid = (a+c)/2;
    if plotFlag == 1
        pause(0.15);
        plot(x_mid,func(x_mid),'-ro');
    end
end
hold off;
x_min = (b+x_mid)/2;

二分法是一種最簡(jiǎn)單的分割方法戈泼，每次迭代都將搜索區(qū)間縮短一半，故二分法的收斂速度是 線性的，收斂比是0.5大猛，收斂速度較慢扭倾。其優(yōu)勢(shì)是每一步迭代的計(jì)算量相對(duì)較少，邏輯簡(jiǎn)單挽绩，而且總能收斂到一個(gè)局部極小點(diǎn)吆录。

Fibonacci 分?jǐn)?shù)法

兔子生兔子問(wèn)題大家很熟悉，其就是典型的Fibonacci數(shù)列琼牧，數(shù)學(xué)定義為：

F_0=1;F_1=1;F_n=F_{n-1}+F_{n-2},n\geq 2

數(shù)列\{F_n\}稱為斐波那契（Fibonacci）數(shù)列，F_n稱為第n個(gè)Fibonacci數(shù)哀卫，相鄰兩個(gè)Fibonacci數(shù)之比稱為Fibonacci分?jǐn)?shù)巨坊。從二分法中，可以得出下面的結(jié)論：

只要在區(qū)間[a,b]內(nèi)任取兩個(gè)不同點(diǎn)此改，并算出他們的函數(shù)值加以比較趾撵，就可以把搜索區(qū)間縮小為[a_1,b]或[a,b_1] ,因?yàn)榭s小后的區(qū)間仍包含極小點(diǎn)。要進(jìn)一步縮小搜索區(qū)間共啃，只需在縮小后的區(qū)間內(nèi)再取一點(diǎn)占调，并與f(a_1) 或f(a_2)比較函數(shù)值大小。按照這樣的步驟迭代進(jìn)行移剪，隨著計(jì)算函數(shù)值次數(shù)的 增加究珊，區(qū)間越來(lái)越小，從而越接近極小點(diǎn)纵苛。

這是分割類方法的通用思想剿涮，即通過(guò)不斷的縮小區(qū)間達(dá)到極值點(diǎn)。Fibonacci 分?jǐn)?shù)法是利用這一思想攻人，只是搜索區(qū)間的長(zhǎng)度不再是二分法的0.5取试，而是采用Fibonacci數(shù)列。

Algorithm 4 Fibonacci 分?jǐn)?shù)法

function x_min = FibonacciSection(func,a,b,toll,plotFlag)
%確保[a,b]為單峰區(qū)間

if nargin < 5
    plotFlag = 0;
end

if nargin < 4
    toll = 10^(-8);
end

if (a>b)
    [a,b]=swap(a,b);
end

%step 1 初始化數(shù)據(jù)
Ln = (b-a)^2/toll;
F(1) = 1;
F(2) = 1;
n = 2;
%step 2 求Fibonacci數(shù)列
while F(n)<Ln
    n = n+1;
    F(n) = F(n-1) + F(n-2);
end

%step 3 初始化x1 x2怀吻，即k = 1
k = 1;
x1 = a+F(n-2)/F(n)*(b-a);
x2 = a+F(n-1)/F(n)*(b-a);
fx1 = func(x1);
fx2 = func(x2);

if plotFlag == 1
    figH = figure();
    abInt = (b-a)/100;
    plot(a:abInt:b,func(a:abInt:b),'-b',a,func(a),'-*r',b,func(b),'-*g');
    hold on;
end

%step 4 ,迭代縮短區(qū)間

while k<n-2
    if fx1<fx2 %如果fx1<fx2瞬浓，則說(shuō)明極小點(diǎn)在a x2區(qū)間內(nèi)
        b = x2;
        x2 = x1;
        fx2 = fx1;
        x1 = a + F(n-k-2)/F(n-k)*(b-a);
        fx1 = func(x1);
    else %反之，則說(shuō)明極小點(diǎn)在x1 b之間
        a = x1;
        x1 = x2;
        fx1 = fx2;
        x2 = a + F(n-k-1)/F(n-k)*(b-a);
        fx2 = func(x2);
    end
    k = k+1;
    if plotFlag == 1
        pause(0.15);
        plot(a,func(a),'-*r',b,func(b),'-*g');
    end
end

%step 5 k = n -2 時(shí),再此比較fx1 和 fx2
%區(qū)間固定在a b之間蓬坡，且包含 x2
if fx1<fx2
    b = x2;
    x2 = x1;
    fx2 = fx1;
else
    a = x1;
end
%step 6 計(jì)算x1 和 fx1 ,通過(guò)判斷得極小點(diǎn)
x1 = x2 - toll*(b-a);
fx1 = func(x1);
if plotFlag == 1
    pause(0.15);
    plot(x1,fx1,'-ro',x2,fx2,'-ob',a,func(a),'-*r',b,func(b),'-*g');
    hold off;
end

if fx1<fx2
    x_min = (a+x2)/2.0;
elseif fx1 == fx2
    x_min = (x1+x2)/2.0;
else
    x_min = (x1+b)/2;
end

end

function [a,b]=swap(a,b)
t=a;
a=b;
b=t;
end

Fibonacci分?jǐn)?shù)法可以證明是最優(yōu)策略猿棉。相對(duì)二分法Fibonacci分?jǐn)?shù)法收斂快，然而開(kāi)始需要確定迭代次數(shù)屑咳，計(jì)算Fibonacci數(shù)列铺根，每步取點(diǎn)繁瑣，各步縮短率不同乔宿。為此位迂，引入黃金分割法。

黃金分割法

黃金分割法內(nèi)分點(diǎn)的原則是：對(duì)稱且每次區(qū)間縮短率\lambda相等。對(duì)稱性來(lái)自Fibonacci分?jǐn)?shù)法掂林，固定縮短率也是改進(jìn)Fibonacci分?jǐn)?shù)發(fā)的不足臣缀，可見(jiàn)黃金分割法和Fibonacci分?jǐn)?shù)法是有聯(lián)系。的確泻帮，可以證明Fibonacci的縮短率在極限情況下就是黃金分割法的縮短率精置，0.618。有興趣的讀者可以查找相關(guān)資料锣杂。

在搜索區(qū)間[a,b]內(nèi)適當(dāng)插入兩點(diǎn),x_1,x_2,x_1<x_2,且在區(qū)間內(nèi)對(duì)稱位置脂倦，計(jì)算其函數(shù)值y_1=f(x_1),y_2=f(x_2)
（1）若y_1<y_2，則極小點(diǎn)必在區(qū)間[a,x_2]內(nèi)元莫，令b=x_2赖阻，新區(qū)間為[a,x_2];
（2）若y_1\geq y_2,則極小點(diǎn)必在區(qū)間[x_1,b]內(nèi)，令a=x_1踱蠢，新區(qū)間為[x_1,b]火欧。

經(jīng)過(guò)函數(shù)值比較 ，區(qū)間縮短一次茎截。新區(qū)間只保留x_1,x_2中的一個(gè)苇侵。

設(shè)原區(qū)間長(zhǎng)度為l，保留區(qū)間長(zhǎng)度為\lambda_1l企锌，區(qū)間縮短率為\lambda_1榆浓。進(jìn)行第二次縮短時(shí)，新點(diǎn)x_3,設(shè)y_1>f(x_3)撕攒，則新區(qū)間為[a,x_3]哀军。設(shè)區(qū)間縮短率為\lambda_2。為了保持相同的區(qū)間縮短率打却，應(yīng)有：
\lambda_2 = \frac{(1-\lambda_1)l}{\lambda_1l}=\frac{1-\lambda_1}{\lambda_1}=\lambda_1
由此可得：\lambda_1 = (\sqrt{5}-1)/2\approx 0.618割法又稱為0.618法杉适。黃金分割法是一種等比例縮短區(qū)間的直接搜索方法，適用于[a,b]區(qū)間上的任何單谷函數(shù)求解極小值問(wèn)題柳击。對(duì)函數(shù)除要求單谷外不作其他任何要求猿推，甚至可以不連續(xù)，因此適應(yīng)面廣捌肴。

Algorithm 5 黃金分割法

function x_min = GoldSection(func,a,b,toll,plotFlag)
%確保[a,b]為單峰區(qū)間
if nargin < 5
    plotFlag = 0;
end

if nargin < 4
    toll = 10^(-8);
end

if (a>b)
    [a,b]=swap(a,b);
end

GOLD = (sqrt(5)-1)/2;

%step 1 初始化x1 x2
x1 = a+(1-GOLD)*(b-a);
x2 = a+GOLD*(b-a);
fx1 = func(x1);
fx2 = func(x2);

if plotFlag == 1
    figH = figure();
    abInt = (b-a)/100;
    xx = a:abInt:b;
    for i = 1:1:length(xx)
        yy(i) = func(xx(i));
    end
    plot(xx,yy,'-b',a,func(a),'-*r',b,func(b),'-*g');
    hold on;
end

%step 2 ,迭代縮短區(qū)間
while abs(a-b)>toll
    if fx1<fx2 %如果fx1<fx2蹬叭，則說(shuō)明極小點(diǎn)在a x2區(qū)間內(nèi)
        b = x2;
        x2 = x1;
        fx2 = fx1;
        x1 = a + (1-GOLD)*(b-a);
        fx1 = func(x1);
    elseif fx1 == fx2
        a = x1;
        b = x2;
        x1 = a+(1-GOLD)*(b-a);
        x2 = a+GOLD*(b-a);
        fx1 = func(x1);
        fx2 = func(x2);       
    else%反之，則說(shuō)明極小點(diǎn)在x1 b之間
        a = x1;
        x1 = x2;
        fx1 = fx2;
        x2 = a + GOLD*(b-a);
        fx2 = func(x2);
    end
    if plotFlag == 1
        pause(0.15);
        plot(a,func(a),'-*r',b,func(b),'-*g');
    end
end

x_min = (a+b)/2;

end

function [a,b]=swap(a,b)
t=a;
a=b;
b=t;
end

黃金分割法和Fibonacci分?jǐn)?shù)法也是線性收斂状知，收斂比率約0.618

二次插值法

二分法秽五、Fibonacci分?jǐn)?shù)法以及黃金分割法都屬于試探法，即試驗(yàn)點(diǎn)的位置是由某種給定的規(guī)則確定的饥悴，并沒(méi)有考慮數(shù)值的分布坦喘，僅僅利用試驗(yàn)點(diǎn)函數(shù)值進(jìn)行大小的比較盲再；插值法試驗(yàn)點(diǎn)的位置是按照函數(shù)近似分布的極小點(diǎn)確定的，即插值法需要利用函數(shù)值本身或其導(dǎo)數(shù)信息瓣铣，所以當(dāng)函數(shù)具有較好的解析性質(zhì)時(shí)答朋，插值法比試探法效果更好。

利用原目標(biāo)函數(shù)上的三個(gè)插值點(diǎn)棠笑，構(gòu)成一個(gè)二次插值多項(xiàng)式梦碗，用該多項(xiàng)式的最優(yōu)解作為原函數(shù)最優(yōu)解的近似解，逐步逼近原目標(biāo)函數(shù)的極小點(diǎn)蓖救，稱為二次插值方法或近似拋物線法洪规。簡(jiǎn)單流程如下圖所示：

圖 2 二次插值法示意圖

Algorithm 6 二次插值法

function x_min = ParabolicInterpolationSection(func,a,b,toll,plotFlag)
%確保[a,b]為單峰區(qū)間,且連續(xù)
if nargin < 5
    plotFlag = 0;
end

if nargin < 4
    toll = 10^(-8);
end

if (a>b)
    [a,b]=swap(a,b);
end

if plotFlag == 1
    figH = figure();
    abInt = (b-a)/100;
    plot(a:abInt:b,func(a:abInt:b),'-b',a,func(a),'-*r',b,func(b),'-*g');
    hold on;
end

%step 1 初始化
x1 = (a+b)/2;
%step 2 迭代縮短區(qū)間
while abs(a-b) > toll
    fa = func(a);
    fx1 = func(x1);
    fb = func(b);
    r = (x1-a)*(fx1-fb);
    q = (x1-b)*(fx1-fa);
    C1 = (x1-a)*r-(x1-b)*q;
    C2 = r-q;
    if C2 == 0 %說(shuō)明三點(diǎn)共線，對(duì)于單峰情況循捺，三點(diǎn)共點(diǎn)了斩例，退出
        break;
    end
    x2 = x1 - 1/2*C1/C2; %計(jì)算拋物線的極值點(diǎn)
    if (x2-a)*(b-x2)<=0 %極值點(diǎn)不在區(qū)間內(nèi)（兩點(diǎn)共點(diǎn)）
        break;
    end    
    fx2 = func(x2);   
    if x2>x1
        if fx1<fx2 %如果x2在x1的右邊，fx1<fx2巨柒，則說(shuō)明極小值在a x2區(qū)間內(nèi)
            b = x2;
            fb = fx2;
        else %如果x2在x1的右邊，fx1>=fx2柠衍，則說(shuō)明極小值在x1 b區(qū)間內(nèi)
            a = x1;
            fa = fx1;
            x1 = x2;
            fx1 = fx2;
        end
    else
        if fx1<fx2%如果x2在x1的左邊洋满，fx1<fx2，則說(shuō)明極小值在x2 b區(qū)間內(nèi)
            a = x2;
            fa = fx2;
        else %如果x2在x1的左邊珍坊，fx1>=fx2牺勾，則說(shuō)明極小值在a x1區(qū)間內(nèi)
            b = x1;
            fb = fx1;
            x1 = x2;
            fx1 = fx2;
        end    
    end 
    
    if plotFlag == 1
        pause(0.15);
        plot(a,fa,'-*r',b,fb,'-*g');
    end
    
end

if plotFlag == 1
    hold off;
end

x_min = (a+b)/2;

end
function [a,b]=swap(a,b)
t=a;
a=b;
b=t;
end

三點(diǎn)二次插值法并沒(méi)有直接用到函數(shù)的導(dǎo)數(shù)信息，且相同迭代次數(shù)下阵漏，可以得到更精確的結(jié)果驻民，其收斂比率為1.3，在有解析表達(dá)式履怯，函數(shù)連續(xù)情況下回还，是很實(shí)用的。但拋物線法也有不收斂的情況[1]叹洲，為此Brent做了改進(jìn)柠硕，見(jiàn)后文Brent's Method。

插值法還有很多运提，比如兩點(diǎn)二次插值蝗柔，三次插值，牛頓法民泵，有理插值法等癣丧，這些方法需要用到導(dǎo)數(shù)信息。下面我們介紹牛頓法栈妆，即一點(diǎn)二次插值法胁编。其他方法如果讀者有興趣了解厢钧，可自行從網(wǎng)上檢索相關(guān)算法。

牛頓法

當(dāng)原函數(shù)存在一階二階連續(xù)可導(dǎo)時(shí)掏呼，可以采用牛頓法進(jìn)行一維搜索坏快，收斂速度快，具有局部二階收斂速度憎夷。牛頓法的思想是用二次函數(shù)逐點(diǎn)近似原目標(biāo)函數(shù)莽鸿，以二次函數(shù)的極小點(diǎn)來(lái)近似原目標(biāo)函數(shù)的極小點(diǎn)，用切線代替狐仙逐漸逼近導(dǎo)數(shù)函數(shù)的根拾给∠榈茫可以理解為當(dāng)目標(biāo)函數(shù)有一階連續(xù)導(dǎo)數(shù)，且二階導(dǎo)數(shù)大于零時(shí)蒋得，函數(shù)的極小值點(diǎn)應(yīng)該滿足極值點(diǎn)存在的必要條件级及，即導(dǎo)數(shù)為0，所以求函數(shù)的極小值點(diǎn)也就是求解函數(shù)一階導(dǎo)數(shù)為0的根额衙。

過(guò)(x_0,f^{\prime}(x_0))點(diǎn)的切線方程為：

y=f^{\prime}(x_0)+f^{\prime\prime}(x_0)(x-x_0)

與x軸的交點(diǎn)x_1為：

x_1=x_0-\frac{f^\prime(x_0)}{f^{\prime\prime}(x_0)}

推廣到k步得到迭代公式：

x_{k+1}=x_k-\frac{f^\prime(x_k)}{f^{\prime\prime}(x_k)}

此外迭代公式也可以由Taylor公式展開(kāi)得到：

在x_k附近用二次函數(shù)來(lái)逼近原目標(biāo)函數(shù)饮焦，故在x_k點(diǎn)用Taylor公式展開(kāi)，保留到二次項(xiàng)：

f(x)\approx f(x_k)+f^\prime(x_k)(x-x_k)+1/2f^{\prime\prime}(x_k)(x-x_k)^2=\varphi(x)

令\varphi (x)=0,x\leftarrow x_{k+1},也可以得到上面的迭代公式窍侧。

Algorithm 7 牛頓法（一維線性搜索）

function x_min = NewtonLinSrch(func,dfunc,ddfunc,a,b,toll,plotFlag)
%func 一階二階連續(xù)可導(dǎo)县踢，且二階導(dǎo)數(shù)大于0
if nargin < 7
    plotFlag = 0;
end

if nargin < 6
    toll = 10^(-8);
end

if (a>b)
    [a,b]=swap(a,b);
end
x1 = (a+b)/2;

if plotFlag == 1
    figH = figure();
    abInt = (b-a)/100;
    plot(a:abInt:b,func(a:abInt:b),x1,func(x1),'-ro');
    hold on;
end

while abs(dfunc(x1))>toll&&ddfunc(x1)>0
    x1 = x1 - dfunc(x1)/ddfunc(x1);
    if (x1-a)*(b-x1)<=0
        break; %如果x1超界，說(shuō)明一階導(dǎo)數(shù)或者二階導(dǎo)數(shù)不滿足使用牛頓法的條件
    end
    if plotFlag == 1
        pause(0.15);
        plot(x1,func(x1),'-ro');
    end
end
x_min = x1;
end

function [a,b]=swap(a,b)
t=a;
a=b;
b=t;
end

Brent's Method

以上精確的一維搜索方法各有優(yōu)缺點(diǎn)伟件，Brent為了在所有特殊情況下都能較好的適用硼啤，提出了Brent's Method[1]。該方法也被收錄在Matlab的優(yōu)化庫(kù)中斧账，即fminbnd函數(shù)谴返。該方法結(jié)合了二次插值方法和黃金分割法，它在任何特殊的情況中咧织，都保持6個(gè)函數(shù)點(diǎn)嗓袱，即a,b,u,v,w,x。其中最小值在a和b之間习绢，x是迭代一次找的最小值對(duì)應(yīng)的函數(shù)點(diǎn)索抓，w是次小點(diǎn)，v是w前一次迭代點(diǎn)毯炮，u是當(dāng)前迭代的函數(shù)點(diǎn)逼肯。可以通過(guò)閱讀小面的matlab代碼來(lái)理清Brent's Method的邏輯桃煎。其核心思想是大區(qū)間下采用二次插值法篮幢，小區(qū)間的時(shí)候采用黃金分割法，來(lái)避免二次插值法在小區(qū)間陷入循環(huán)的弊病为迈。幾點(diǎn)需要注意[1]：

1三椿、二次插值使用v,w,x三點(diǎn)缺菌；
2、插值出來(lái)的拋物線極值點(diǎn)一定在區(qū)間[a,b]內(nèi)搜锰；
3伴郁、x 的移動(dòng)步長(zhǎng)不大于上一次的一半（[1]中說(shuō)這樣做可以使得插值計(jì)算的這一步收斂在比較好的點(diǎn)上，避免nonconvergent limit circle）

Algorithm 8 Brent's Method

function x_min = BrentMethod(func,a,b,c,tol,iterNum,plotFlag)
%Brent's Method fminbnd

if nargin < 7
    plotFlag = 0;
end

if nargin < 6
    iterNum = 100;
end

if nargin < 5
    tol = 10^(-8);
end

if (a-b)*(b-c)<=0
    x_min = 0;
    disp('a<b<c or a>b>c is needed!');
    return ;
end

if (a>c)
    b = a;
    a = c;
else
    b = c;
end

if plotFlag == 1
    figH = figure();
    abInt = (b-a)/100;
    plot(a:abInt:b,func(a:abInt:b));
    hold on;
end

GOLD = 1 - (sqrt(5)-1)/2.0;

x = b;
w = b;
v = b;

fw = func(w);
fx = fw;
fv = fw;

e = 0;
d = 0;
for i=1:1:iterNum
    xm = (a+b)/2.0;
    tol1 = tol*abs(x)+eps;
    tol2 = 2*tol1;
    if plotFlag == 1
        pause(0.15);
        plot(x,fx,'-ro');
    end
    
    if abs(x-xm) <= (tol2-0.5*(b-a))
        x_min = x;
        return;
    end
    
    if abs(e)>tol1 %這種情況下是用二次插值法
        r = (x-w)*(fx-fv);
        q = (x-v)*(fx-fw);
        p = (x-v)*q - (x-w)*r;
        q = 2.0*(q-r);
        if q>0
            p = -p;
        end
        
        q = abs(q);
        etemp = e;
        e = d;
        
        if abs(p) >= abs(0.5*q*etemp)||p<=q*(a-x)||p>=q*(b-x)
            %采取黃金分割法得到更大的兩段
            if x>=xm %從a蛋叼，x焊傅，b區(qū)間段中 找最大的一段，乘以GOLD作為下一次的步長(zhǎng)
                e = a-x;
            else
                e = b-x;
            end
            d = GOLD*e;%二次插值法不被接受狈涮，采用golden section
        else
            d = p/q;
            u = x + d; %采用二次插值法
            if u-a<tol2||b-u<tol2 %如果u值很接近a或者b狐胎，將步長(zhǎng)設(shè)為xm和x的長(zhǎng)度
                d = MySignFunc(tol1,xm-x);
            end
        end
        
    else %采用黃金分割
        if x>=xm
            e = a-x;
        else
            e = b-x;
        end
        d = GOLD*e;%二次插值法不被接受，采用golden section
    end
    
    if abs(d) >= tol1 %步長(zhǎng)選擇tol1和d中較小的一個(gè)
        u = x+d;
    else
        u = x+MySignFunc(tol1,d);
    end
    
    fu = func(u);
    if fu<=fx %如果fu小于fx,說(shuō)明下次迭代為區(qū)間不是在[a,x]歌馍，就是在[x,b]
        if u>=x %如果u>=x握巢，則在[x,b]，反之在[a,x]
            a = x;
        else
            b = x;
        end
        v = w;w = x;x = u;
        fv = fw;fw = fx;fx = fu;
    else%反之松却，說(shuō)明下次迭代區(qū)間不是[a,u],就是[u,b]
        if u<x
            a = u;
        else
            b = u;
        end
        
        if fu<=fw || w==x
            v = w; w = u;
            fv = fw; fw = fu;
        else if fu<=fv||v==x||v==w
                v=u;
                fv=fu;
            end
        end
    end
end
end

function a = MySignFunc(a,x)
a = abs(a);
if x<0
    a = -a;
end
end

參考文獻(xiàn)

[1] Numerical Recipes, William H. Press

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 人面猴
    序言：七十年代末暴浦，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子晓锻，更是在濱河造成了極大的恐慌歌焦，老刑警劉巖，帶你破解...
    沈念sama閱讀 222,183評(píng)論 6贊 516
  • 死咒
    序言：濱河連續(xù)發(fā)生了三起死亡事件带射，死亡現(xiàn)場(chǎng)離奇詭異同规，居然都是意外死亡循狰，警方通過(guò)查閱死者的電腦和手機(jī)窟社，發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 94,850評(píng)論 3贊 399
  • 救了他兩次的神仙讓他今天三更去死
    文/潘曉璐 我一進(jìn)店門(mén)，熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)绪钥，“玉大人灿里，你說(shuō)我怎么就攤上這事〕谈梗” “怎么了匣吊？”我有些...
    開(kāi)封第一講書(shū)人閱讀 168,766評(píng)論 0贊 361
  • 道士緝兇錄：失蹤的賣姜人
    文/不壞的土叔 我叫張陵，是天一觀的道長(zhǎng)寸潦。 經(jīng)常有香客問(wèn)我色鸳，道長(zhǎng)，這世上最難降的妖魔是什么见转？ 我笑而不...
    開(kāi)封第一講書(shū)人閱讀 59,854評(píng)論 1贊 299
  • ?港島之戀（遺憾婚禮）
    正文 為了忘掉前任命雀，我火速辦了婚禮，結(jié)果婚禮上斩箫，老公的妹妹穿的比我還像新娘吏砂。我一直安慰自己撵儿，他們只是感情好，可當(dāng)我...
    茶點(diǎn)故事閱讀 68,871評(píng)論 6贊 398
  • 惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
    文/花漫 我一把揭開(kāi)白布狐血。 她就那樣靜靜地躺著淀歇，像睡著了一般。 火紅的嫁衣襯著肌膚如雪匈织。 梳的紋絲不亂的頭發(fā)上浪默，一...
    開(kāi)封第一講書(shū)人閱讀 52,457評(píng)論 1贊 311
  • 城市分裂傳說(shuō)
    那天，我揣著相機(jī)與錄音报亩，去河邊找鬼浴鸿。 笑死，一個(gè)胖子當(dāng)著我的面吹牛弦追，可吹牛的內(nèi)容都是我干的岳链。 我是一名探鬼主播，決...
    沈念sama閱讀 40,999評(píng)論 3贊 422
  • 雙鴛鴦連環(huán)套：你想象不到人心有多黑
    文/蒼蘭香墨 我猛地睜開(kāi)眼劲件，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼掸哑！你這毒婦竟也來(lái)了？” 一聲冷哼從身側(cè)響起零远，我...
    開(kāi)封第一講書(shū)人閱讀 39,914評(píng)論 0贊 277
  • 萬(wàn)榮殺人案實(shí)錄
    序言：老撾萬(wàn)榮一對(duì)情侶失蹤苗分，失蹤者是張志新（化名）和其女友劉穎，沒(méi)想到半個(gè)月后牵辣，有當(dāng)?shù)厝嗽跇?shù)林里發(fā)現(xiàn)了一具尸體摔癣，經(jīng)...
    沈念sama閱讀 46,465評(píng)論 1贊 319
  • ?護(hù)林員之死
    正文 獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,543評(píng)論 3贊 342
  • ?白月光啟示錄
    正文 我和宋清朗相戀三年纬向，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了择浊。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,675評(píng)論 1贊 353
  • 活死人
    序言：一個(gè)原本活蹦亂跳的男人離奇死亡逾条，死狀恐怖琢岩，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情师脂，我是刑警寧澤担孔，帶...
    沈念sama閱讀 36,354評(píng)論 5贊 351
  • ?日本核電站爆炸內(nèi)幕
    正文 年R本政府宣布，位于F島的核電站吃警，受9級(jí)特大地震影響糕篇，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜酌心，卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,029評(píng)論 3贊 335
  • 男人毒藥：我在死后第九天來(lái)索命
    文/蒙蒙 一拌消、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧谒府，春花似錦拼坎、人聲如沸浮毯。這莊子的主人今日做“春日...
    開(kāi)封第一講書(shū)人閱讀 32,514評(píng)論 0贊 25
  • 一樁弒父案泰鸡，背后竟有這般陰謀
    文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)债蓝。三九已至，卻和暖如春盛龄，著一層夾襖步出監(jiān)牢的瞬間饰迹，已是汗流浹背。 一陣腳步聲響...
    開(kāi)封第一講書(shū)人閱讀 33,616評(píng)論 1贊 274
  • 情欲美人皮
    我被黑心中介騙來(lái)泰國(guó)打工余舶， 沒(méi)想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留啊鸭，地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,091評(píng)論 3贊 378
  • 代替公主和親
    正文 我出身青樓匿值，卻偏偏與公主長(zhǎng)得像赠制，于是被迫代替她去往敵國(guó)和親。 傳聞我的和親對(duì)象是個(gè)殘疾皇子挟憔，可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,685評(píng)論 2贊 360

推薦閱讀更多精彩內(nèi)容