擬牛頓迭代方法初始值的研究

張安玲

(長治學(xué)院 數(shù)學(xué)系,山西 長治 046011)

0 引言

擬牛頓法(Quasi-Newton Methods)是求解非線性優(yōu)化問題的一種有效方法之一，它最大的優(yōu)點是在參數(shù)初始值選擇恰當(dāng)?shù)那闆r下，收斂速度快，精確度高[1].但是其收斂性和性能在很大程度上要依賴于初始值的選取[2].如果擬牛頓法選取的迭代初始值接近真實解，則容易找到最優(yōu)解，并且具有局部快速收斂的優(yōu)點，擬牛頓法會表現(xiàn)出較強的搜索能力；如果初始值離最優(yōu)解較遠(yuǎn)，擬牛頓法運行通常失敗[3]，所以提供好的初始值對于擬牛頓法來說是非常重要的.

粒子群優(yōu)化算法，具有較強的全局搜索能力，但粒子群優(yōu)化算法的局部搜索能力較差，當(dāng)搜索到達(dá)真實解附近時，其搜索速度明顯減慢甚至終止[1-3].

針對擬牛頓法和粒子群優(yōu)化算法的特點，對所求問題在可行解區(qū)域范圍內(nèi)進(jìn)行大范圍的搜索，等進(jìn)化到一定程度，把當(dāng)代的最好點作為擬牛頓法的初始點，再運行擬牛頓法.這樣，粒子群優(yōu)化算法就能給擬牛頓法提供好的初始值，從而解決擬牛頓法對初始值的敏感問題，保證擬牛頓法的成功，同時加快搜索速度，提高解的精度.

1 算法設(shè)計

在非線性優(yōu)化問題中，為了解決擬牛頓法的初始值問題，提出以下算法.

算法的主要步驟：

Step1粒子群優(yōu)化算法運行M代；

Step2以Step1返回的當(dāng)前全局最優(yōu)個體作為擬牛頓法的初始值x(1)∈Rn，允許誤差ε>0；

Step3置H1=In(單位矩陣)，計算出在x(1)處的梯度g1=f(x(1))，置k=1；

Step4 令d(k)=-Hkgk；

Step5 從x(k)出發(fā)，沿方向d(k)搜索，求步長λk，使它滿足

令

x(k+1)=x(k)+λkd(k)；

Step7 若k=n，則令x(1)=x(k+1)，返回Step3；否則，進(jìn)行Step8；

Step8 令

gk+1=f(x(k+1))，p(k)=x(k+1)-x(k)，q(k)=gk+1-gk

利用

計算Hk+1，置k:=k+1，返回Step4.

該算法是由粒子群優(yōu)化算法和擬牛頓法結(jié)合而成.算法流程是先讓粒子群優(yōu)化算法運行M代，把當(dāng)代的最好點作為擬牛頓法的初始值，然后循環(huán)執(zhí)行擬牛頓法，直到達(dá)到要求精度或達(dá)到最大迭代數(shù)停止.

粒子群優(yōu)化算法是給擬牛頓法提供好的初始點，并沒有改變原擬牛頓法的收斂性，所以本文算法具有與原擬牛頓法相同的收斂性.

2 數(shù)值計算與分析

選取三個典型函數(shù)對該算法進(jìn)行驗證：

利用本文算法對以上測試函數(shù)進(jìn)行數(shù)值仿真計算，計算結(jié)果見表1.

從表1可知，對一般優(yōu)化方法難以優(yōu)化的F1～F3函數(shù)，本文算法都以100%的概率成功地找到了全局最優(yōu)解，并且求解精度高、運算速度快.

表1 本文算法對F1～F3的數(shù)值結(jié)果

當(dāng)M=1時，粒子群優(yōu)化算法運行1次，然后就開始執(zhí)行擬牛頓法，此時粒子群優(yōu)化算法的作用相當(dāng)于給擬牛頓法隨機(jī)提供一個初始值.所以當(dāng)M=1時，本文算法退化為一般的擬牛頓法.

表2 本文算法和擬牛頓法的比較

注：M=1表示擬牛頓法，M=500或300表示本文算法；精度達(dá)到10-12認(rèn)為算法成功.

從表2可知，對函數(shù)F1，擬牛頓法的成功率是75%，但對有大量局部極小點的多峰函數(shù)F2與F3，擬牛頓法就完全運行失敗.其主要原因是擬牛頓法只具有局部搜索能力，并且在沒有被賦予好的初始值時，算法的成功率很低.其原因是擬牛頓法沒有全局搜索能力而且對初始值非常敏感，在沒有被賦予好的初始值時，算法往往失敗.而本文算法的成功率達(dá)到了100%，這充分說明粒子群優(yōu)化算法為擬牛頓法提供了很好的初始值，從而保證了擬牛頓法的成功.

為了進(jìn)一步了解粒子群迭代數(shù)M對擬牛頓法的影響，以函數(shù)F3為例進(jìn)行分析.具體見表3.

表3 不同初始值對擬牛頓法的影響

注：精度達(dá)到10-12認(rèn)為算法成功；M取值越大，提供給擬牛頓法的初始值越好.

從表3可知，當(dāng)M=1時，算法的成功率是0%，表明使用擬牛頓法的失敗率是100%；當(dāng)M的取值增大時，算法的成功率也在增大.這是因為：當(dāng)M取值較小時，粒子群優(yōu)化算法迭代次數(shù)少，獲得解的精度低，也就是傳給擬牛頓法迭代的初始值較差，擬牛頓法在沒有獲得好的初始值情況下運行失??；相反，當(dāng)M取值較大時，粒子群優(yōu)化算法迭代次數(shù)多，獲得解的精度相對高，從而傳給擬牛頓法的初始值較好，此時，擬牛頓法就可以充分發(fā)揮它的局部精細(xì)搜索性，所以成功率比較大.這充分表明先運行若干代粒子群優(yōu)化算法，然后把當(dāng)代最好點作為擬牛頓法的初始值，這種做法能有效解決擬牛頓法的初始值問題，從而保證擬牛頓法的成功率.

3 結(jié)束語

本文提出了一種為擬牛頓法提供好的初始值的方法.該方法首先是粒子群優(yōu)化算法在可行解區(qū)域范圍內(nèi)用隨機(jī)選取的初始值運行若干迭代，把得到的最好解作為擬牛頓法的初始值，然后擬牛頓法利用這組初始值進(jìn)行迭代搜索.實驗結(jié)果表明，該方法為擬牛頓法提供了較好的初始值，從而有效地解決了擬牛頓法對初始值敏感的問題，在很大程度上提高了擬牛頓法的成功率.另外，本文算法并沒有改變擬牛頓法的收斂性，具有與原擬牛頓法相同的收斂性.