高等數學中關于擴展的非擬牛頓算法的全局收斂性

孟紅軍

(滁州城市職業學院教育系 安徽 滁州 239000)

近年來，關于擬牛頓算法收斂性的研究一直是非線性最優化算法理論研究的熱點。在理論研究方面,帶非精確線性搜索的擬牛頓算法的收斂性一直是人們感興趣的問題。擬牛頓法的基本思想就是將牛頓方向中的▽2f(xk)用一個對稱正定的矩陣Bk近似替代。在眾多求解無約束優化問題的算法中，牛頓法因其具有二次收斂性而頗受歡迎.但牛頓法也存在一個非常明顯的缺陷，即：當▽2f(xk)不正定時,無法保證算法產生的方向。曹邦興等人(2019)提出來通過比較基本與修正牛頓算法的優缺點來解決各自問題的缺陷，從而求解無約束函數的逼近效果[1]。何國良等人(2019)通過對經典迭代算法的演化，簡歷了分階導數的迭代格式，進一步擴展了牛頓迭代方法[2]。陳宇等人(2019)提出利用軟場效應與稀疏擬牛頓算法結合，重建算法數學模型，可以提高圖像生成質量[3]。鑒于此，可以看出通過綜合利用信息δk,γk與fk,建立了的校正公式,其導出擴展的非擬牛頓算法通過驗證證明了算法對一致凸函數的全局收斂性。

一、算法的引理擴展

(一)擴展的非擬牛頓算法

(1)

由此出發導出擴展的非擬牛頓算法。先考慮秩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是極值問題的唯一最優解，這里·k是Frobenius范數[4].

校正(8)略有缺陷，不能保證正定傳遞性的同時在迭代過程中的絕對值較小引發了數值的不穩定現象。

(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和正常數ε，令k:=0;若gk≤ε，停止迭代，輸出xk；解線性方程組Bkd=-gk，求得dk;步長λk由某種線性搜索確定[5].

二、全局收斂性

(一)假設驗證

目標函數f(x)在Rn上二階連續可微且有下界，且f(x)在集合H?Rn上一致凸，即存在正數M>m>0，使得對所有的xH及，zRn，有不等式mz2≤zTG(x)z≤Mz2,其中G(x)為f(x)的Hessian陣,·表示歐式范數或相應的矩陣范數.

記水平集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，由算法產生的矩陣列{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)

其中參數α(α,1),對某個k有gk=0或者如(23)所示：

(23)

證明：利用反證法來驗證，首先需要做出假設即(22)不成立，則存在正數P使得所有k值，有gk≥p>0. 在此條件下，當δ≠0時，算法產生的矩陣列{Bk}對稱正定，算法產生的函數序列{fk}單調下降，又由f(x)有下界，因此當k→∞時，有fk+1-fk→0.

當k→∞時，有δk=xk+1-xk→0.由f(x)的連續性知，對與之對應的函數列亦有{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),即分解唯一.

三、結論

本文中的非擬牛頓算法能夠使目標函數在一致凸，且采用Wolfe-Powell不精確線性搜索和Gold-stein非精確線性搜索的條件下始終產生下降方向。我們還分析證明了該算法在這兩種線性搜索下的全局收斂性, 說明它是一種有效的算法, 可以用來有效的解決一些實際生活中的無約束最優化問題.擬牛頓法用BK+1替代▽2f(xk+1)克服了牛頓法中計算函數f的二階導數的困難，若Bk保持正定，使得算法具有下降的性質且收斂速度快等優點，而非牛頓算法在擬牛頓算法的基礎上，當δk充分小時，用Bk+1替代▽2f(xk)，使非擬牛頓方程不僅利用了函數梯度值信息，還利用了函數值的信息，從而使算法具有良好的數值效果。