孟紅軍

(滁州城市職業(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)

(二)算法引理1

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)

其中θ稱為擴展的非擬牛頓校正公式.

(三)算法引理2

設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ù)值效果。