孟紅軍
(滁州城市職業(yè)學院教育系 安徽 滁州 239000)
近年來,關于擬牛頓算法收斂性的研究一直是非線性最優(yōu)化算法理論研究的熱點。在理論研究方面,帶非精確線性搜索的擬牛頓算法的收斂性一直是人們感興趣的問題。擬牛頓法的基本思想就是將牛頓方向中的▽2f(xk)用一個對稱正定的矩陣Bk近似替代。在眾多求解無約束優(yōu)化問題的算法中,牛頓法因其具有二次收斂性而頗受歡迎.但牛頓法也存在一個非常明顯的缺陷,即:當▽2f(xk)不正定時,無法保證算法產(chǎn)生的方向。曹邦興等人(2019)提出來通過比較基本與修正牛頓算法的優(yōu)缺點來解決各自問題的缺陷,從而求解無約束函數(shù)的逼近效果[1]。何國良等人(2019)通過對經(jīng)典迭代算法的演化,簡歷了分階導數(shù)的迭代格式,進一步擴展了牛頓迭代方法[2]。陳宇等人(2019)提出利用軟場效應與稀疏擬牛頓算法結合,重建算法數(shù)學模型,可以提高圖像生成質量[3]。鑒于此,可以看出通過綜合利用信息δk,γk與fk,建立了的校正公式,其導出擴展的非擬牛頓算法通過驗證證明了算法對一致凸函數(shù)的全局收斂性。
(1)
由此出發(fā)導出擴展的非擬牛頓算法。先考慮秩1校正如(2)所示:
Bk+1=Bk+uνT
(2)
其中待定向量u,νRn.要求Bk+1還要滿足條件如(3)所示:
Bk+1δk=αδk
(3)
(4)
(5)
再由(4),u記為如(6)所示:
(6)
將(6)代人(2)得到秩1校正式,如(7)所示:
(7)
(8)
BL(Rn),ν,δkRn,且νTδk≠0,則由(8)定義的Bk+1是極值問題的唯一最優(yōu)解,這里·k是Frobenius范數(shù)[4].
校正(8)略有缺陷,不能保證正定傳遞性的同時在迭代過程中的絕對值較小引發(fā)了數(shù)值的不穩(wěn)定現(xiàn)象。
(9)
由此關系,可以證明由(9)定義的{Bj}有一極限Bk+1使得如(10)所示:
(10)
且Bk+1滿足(2)及(5)。因此,(10)為對稱秩2校正式。
令ν=δk,結合(4)與(10)可以寫成如(11)所示:
(11)
(12)
其中θ稱為擴展的非擬牛頓校正公式.
設Bk對稱正定,φ≥0,若Qk>0,(k=0,1,2),則校正(12)使Bk+1保持對稱正定.
由此導出求解問題(3)擴展的非擬牛頓算法:選擇初始點x0Rn,初始對稱正定矩陣B0Rn×n和正常數(shù)ε,令k:=0;若gk≤ε,停止迭代,輸出xk;解線性方程組Bkd=-gk,求得dk;步長λk由某種線性搜索確定[5].
目標函數(shù)f(x)在Rn上二階連續(xù)可微且有下界,且f(x)在集合H?Rn上一致凸,即存在正數(shù)M>m>0,使得對所有的xH及,zRn,有不等式mz2≤zTG(x)z≤Mz2,其中G(x)為f(x)的Hessian陣,·表示歐式范數(shù)或相應的矩陣范數(shù).
記水平集H={xRn|f(x)≤f(x0)有界,并假設存在x1,使水平集D={x|f(x)≤f(x1)}?H.若定義則由假設A知即這表明如(13)所示:
(13)
(14)
這說明δk≠0時,Qk>0總成立.從而由引理2知:對任意初始點x1及任意初始正定對稱矩陣B1,由算法產(chǎn)生的矩陣列{Bk}正定.
(15)
當φ=0時等號成立.
(16)
(17)
Ψ(Bk)=tr(Bk)-ln[det(Bk)]
(18)
其中Bk為正矩陣.若Bk的全體特征值為μj,j=1,2,3…n,則如(19)所示:
(19)
注意到對任意t>0,總有W(t)=t-lnt≥1,所以如(20)所示:
l-t+lnt≤0,t>0,
(20)
在假設A下,當φ[0,1],δk≠0時,如(21)所示:
(21)
(三 )定理證明
在假設A下,擴展的非擬牛頓算法在Wolfe-Powell線性搜索下如(22)所示:
(22)
其中參數(shù)α(α,1),對某個k有gk=0或者如(23)所示:
(23)
證明:利用反證法來驗證,首先需要做出假設即(22)不成立,則存在正數(shù)P使得所有k值,有gk≥p>0. 在此條件下,當δ≠0時,算法產(chǎn)生的矩陣列{Bk}對稱正定,算法產(chǎn)生的函數(shù)序列{fk}單調下降,又由f(x)有下界,因此當k→∞時,有fk+1-fk→0.
當k→∞時,有δk=xk+1-xk→0.由f(x)的連續(xù)性知,對與之對應的函數(shù)列亦有{fk}k1亦有fk+1-fk→0(k→∞,kK1).另外有當k→∞時,如(24)所示:
(24)
事實上,
于是?z(k)C,f(z)=f0(z)+f1(z)+…+fn(z).
f0(z)-g0(z)≡0,即f0(z)≡g0(z).故當|z(k)|→∞時,fi(z)→0(i=1,…,n),f0(z(k))被唯一確定.顯然,當n=1時,f0(z)=g0(z),f1(z)=g1(z),即分解唯一.
本文中的非擬牛頓算法能夠使目標函數(shù)在一致凸,且采用Wolfe-Powell不精確線性搜索和Gold-stein非精確線性搜索的條件下始終產(chǎn)生下降方向。我們還分析證明了該算法在這兩種線性搜索下的全局收斂性, 說明它是一種有效的算法, 可以用來有效的解決一些實際生活中的無約束最優(yōu)化問題.擬牛頓法用BK+1替代▽2f(xk+1)克服了牛頓法中計算函數(shù)f的二階導數(shù)的困難,若Bk保持正定,使得算法具有下降的性質且收斂速度快等優(yōu)點,而非牛頓算法在擬牛頓算法的基礎上,當δk充分小時,用Bk+1替代▽2f(xk),使非擬牛頓方程不僅利用了函數(shù)梯度值信息,還利用了函數(shù)值的信息,從而使算法具有良好的數(shù)值效果。