幾個修正擬牛頓算法的收斂性分析

《幾個修正擬牛頓算法的收斂性分析》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、第20卷第4期南通職業(yè)大學(xué)學(xué)報Vol.20No.42006年12月JOURNALOF南NA通NT職ON業(yè)GV大OC學(xué)ATI學(xué)ON報ALCOLLEGEDec2.0200606年!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!幾個修正擬牛頓算法的收斂性分析王海濱(南通職業(yè)大學(xué)基礎(chǔ)部,江蘇南通226007)摘要:將幾個擬牛頓算法推廣到一類新擬牛頓方程,得到幾個修正擬牛頓算法;在目標(biāo)函數(shù)為一致凸的條件下,證明了它們都具有全局收斂性。關(guān)鍵詞:新擬牛頓方程;修正擬牛頓算法;全局收斂性中圖分類號:O224文獻標(biāo)識碼:A文

2、章編號:1008-5327(2006)04-0068-041問題的提出6Ttk=(f(xk)-f(xk+1)+skgk+1)-2(3)sTy針對無約束最優(yōu)化問題:minf(x)x∈Rn,其kk[2]基于目標(biāo)函數(shù)局部二次模型近似,采用與nYuan中f:R→R是一個連續(xù)可微函數(shù),擬牛頓法是一傳統(tǒng)方式不同的插值條件,提出了一個類似公式,類重要的數(shù)值方法。不僅由于其實用效果較好,而它仍采取式(3)的形式,但其中的tk改取為:且在收斂性理論的研究方面也取得了相當(dāng)?shù)某晒＿@類算法的關(guān)鍵是Bk的選取,Bk的選取方式t=2(f(x)-f(x)+sTg)(4)kkk+1kk+1T不同,就對應(yīng)

3、不同的擬牛頓算法,其中最著名的是skyk[3]基于目標(biāo)函數(shù)的局部二次模型近似,亦提出BFGS算法,它采用的迭代形式為:Jiaoxk+1=xk+!kdk了一個類似公式,其中tk改取為:其中:x1是初始點,xk是當(dāng)前點,!k>0是步t=2(1-θ)(f(x)-f(x)-sTg)+θ,θ∈[0,1]kk+1kkkT-1skyk長,dk是搜索方向,一般定義為dk=-Bkgk;這(5)里,Bk為n×n階矩陣,gk=$f(xk),一般要求Bk文獻[4]在以上這些算法的基礎(chǔ)上,總結(jié)了一類改對稱正定,且滿足擬牛頓方程進的BFGS算法,其擬牛頓校正公式為:Bk+1sk=ykBssTByyTs

4、k=xk+1-xk(1)B=B-kkkk+tkk(6)k+1kkTTyk=gk+1-gk(2)skBkskskykBk由以下迭代公式確定:其中tk滿足(1-tk(≤t′‖sk‖(7)BksksTBkykyT對所有k成立,t′為一常數(shù)。kkBk+1=Bk-+當(dāng)式(6)中tk取式(3)時,則得到Biggs算法;sTBssTykkkkk取式(4)時,則得到Y(jié)uan算法;取式(5)時,則得在此基礎(chǔ)上Biggs[1]基于目標(biāo)函數(shù)局部非二次模到Jiao算法。型近似,認(rèn)為Bk應(yīng)修改為:基于傳統(tǒng)擬牛頓方程基礎(chǔ)上的上述幾個擬牛頓BssTByyTB=B-kkkk+tkk算法,其收斂性問題已得到

5、解決。作為對傳統(tǒng)擬牛頓k+1kksTBssTykkkkk方程的改進,文獻[5]提出了一類新擬牛頓方程:其中sk,yk仍用式(1)、(2)定義,且Bk+1sk=y’k(8)收稿日期:2006-10-20項目項目:江蘇省高校自然科學(xué)研究指導(dǎo)性項目(05KJD110174)作者簡介:王海濱(1968-),女,江蘇南通人,講師、碩士,研究方向為最優(yōu)化理論與算法。68第4期王海濱:幾個修正擬牛頓算法的收斂性分析!kB6y!k=yk+sk(9)當(dāng)校正公式(15)中的’tk取’tk=[f(xk)TTskyksky’kT!k=6(fk-fk+1)+3(gk+gk+1)sk(10)-f(x)

6、+sTg]-2時,就得到修正Biggs算法(y’k+1kk+1k其中sk、yk仍用式(1)、(2)定義。B取法同式(16))。其中參數(shù)’t不一定都大于零;k將上述幾個擬牛頓算法推廣到新擬牛頓方BB程,即得到幾個修正的擬牛頓算法。下面給出基為了保證Biggs算法的適定性,當(dāng)’t<0時,取’t=kk新擬牛頓方程的幾個修正擬牛頓算法模型,并在B"0("0為一正數(shù)),從而限制參數(shù)’tk>0。假設(shè)目標(biāo)函數(shù)一致凸的條件下,證明它們具有全局收斂性。當(dāng)校正公式(15)中’t取’tY=2(f(x)-kkkTsky’k2基于新擬牛頓方程的幾個修正擬牛頓T取法算法模型f(xk+1)+skgk+1

7、)時,就得到修正Yuan算法(y’kYn同式(16))。當(dāng)目標(biāo)函數(shù)一致凸時,易知’t>0。因步1:給定初始點x1∈R,選取n×n對稱正定矩k陣B1,令k=1此,算法是適定的。步2:計算gk=#f(xk),若‖gk‖=0,則停;否則轉(zhuǎn)步3當(dāng)校正公式(15)中’tk取-1J步3:令dk=-Bkgk’t=2(1-θ)(f(x)-f(x)-sTg)+θ,θ∈[0,1]kk+1kkksTy’步4:令xk+1=xk+!kdkkk其中,!k由如下wolf線搜索確定:給定時,就得到修正Jiao算法(y’k取法同式(16))。當(dāng)目1