• 
    

    
    

      99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

      求解大規(guī)模非線性單調(diào)方程組的修正HS投影算法

      2020-03-25 05:27:00王松華黎勇黃必昌
      關(guān)鍵詞:共軛收斂性單調(diào)

      王松華,黎勇,黃必昌

      (百色學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院,廣西 百色 533000)

      0 引 言

      本文考慮如下非線性單調(diào)方程組

      F(x)=0,x∈Rn,

      (1)

      其中函數(shù)F是連續(xù)可微且單調(diào)的,對?x,y∈Rn,有

      〈F(x)-F(y),x-y〉≥0。

      (2)

      minQ(x),x∈Rn,

      (3)

      一般地,好的共軛梯度法取決于好的共軛梯度方向和一個非精確線搜索技術(shù)。搜索方向在很大程度上決定了搜索效率,而搜索方向的充分下降和信賴域性質(zhì)對共軛梯度法的全局收斂性起到積極作用[7-8]。M.V.Solodov等[9]提出將投影技術(shù)應(yīng)用于大型非線性方程,取得了有效成果。目前,結(jié)合投影技術(shù),將共軛梯度法應(yīng)用到大規(guī)模非線性方程組成為最優(yōu)化領(lǐng)域研究的一個熱點(diǎn)[10-14]。同時,針對單調(diào)非線性問題,文獻(xiàn)[15]給出著名的線搜索技術(shù),能有效解決非線性大規(guī)模問題,其公式為

      (4)

      其中αk=max{s,ρs,ρ2s,…},σ>0,s>0,ρ∈(0,1)。

      本文在文獻(xiàn)[5]的基礎(chǔ)上,設(shè)計一個新的搜索方向,采用M.V.Solodov等[9]的投影技術(shù),結(jié)合文獻(xiàn)[15]線搜索方法,提出一個求解大規(guī)模非線性單調(diào)方程組的修正HS投影算法。

      1 修正的HS投影算法

      共軛梯度法迭代公式的一般形式為

      xk+1=xk+αkdk,

      (5)

      式中:xk為當(dāng)前迭代點(diǎn);xk+1為下一個迭代點(diǎn);αk為步長,由某種線搜索確定;dk為搜索方向,迭代公式定義為

      (6)

      其中,βk為一個共軛參數(shù),F(xiàn)k為F(xk)的簡寫。

      令zk=xk+αkdk,有F(zk)T(x-zk)>0。如果對某個點(diǎn)x*滿足f(x*)=0,由函數(shù)F的單調(diào)性質(zhì)有F(zk)T(x-zk)≤0。則通過超平面

      Hk={x∈Rn|F(zk)T(x-zk)=0}

      嚴(yán)格將當(dāng)前迭代點(diǎn)xk從式(1)的解中分離出來,M.V.Solodovy等[9]建議將當(dāng)前點(diǎn)xk投影到超平面Hk方便確定下一個迭代點(diǎn),即

      (7)

      式(7)是有效的,不僅得到了較好的數(shù)值結(jié)果,而且具有較好的理論性質(zhì)。

      針對大規(guī)模無約束優(yōu)化問題,經(jīng)典共軛梯度法有PRP、HS、FR、CD、DY和LS等[16]。經(jīng)典的PRP方法、HS方法和LS方法在數(shù)值結(jié)果表現(xiàn)上非常有效,但是其全局收斂性并不令人滿意。文獻(xiàn)[5]在文獻(xiàn)[17]的基礎(chǔ)上修正了βPRP公式,該公式具有充分下降性,在標(biāo)準(zhǔn)WWP線搜索上算法全局收斂,數(shù)值結(jié)果良好,但該βPRP公式不具有信賴域性質(zhì)。同時文獻(xiàn)[5]給出了修正βHS公式,并給出了相應(yīng)算法的初步數(shù)值試驗結(jié)果和分析,但是沒有證明該算法的充分下降性和全局收斂性。修正βHS公式[5]定義為

      受此啟發(fā),本文在文獻(xiàn)[5]的基礎(chǔ)上,結(jié)合文獻(xiàn)[7]和[14]關(guān)于共軛參數(shù)的修正方法,設(shè)計一個新的搜索方向dk+1,

      dk+1=

      (8)

      其中,μ>1/4,λ≥2,γ≥2。

      算法1

      步驟3 采用線搜索式(4)計算步長αk;通過式(8)計算搜索方向dk。

      步驟4 令迭代公式為zk=xk+αkdk。

      步驟6 令k:=k+1,轉(zhuǎn)步驟2。

      2 充分下降性和信賴域性質(zhì)

      首先證明算法1的搜索方向dk具有充分下降和信賴域性質(zhì)。

      引理1 搜索方向dk由式(8)定義,則存在c2>c1>0,使得下式成立:

      (9)

      (10)

      首先證明不等式(9)成立。

      證明k=0時,不等式(9)成立。以下證明k≥1時,不等式(9)成立。

      根據(jù)式(8),結(jié)合范數(shù)性質(zhì),得到

      由式(9)可直接推導(dǎo)出式(10)的左半部分,下面證明式(10)的右半部分。

      3 全局收斂性分析

      假設(shè)1

      (1)式(1)的解集非空,且水平集Ω={x∈Rn:F(x)≤F(x1)}有界。

      (2)函數(shù)F:Rn→Rn是Lipschitz連續(xù)的,即?L>0,使得

      (11)

      即存在一個常數(shù)?=2ωL>0,使得

      (12)

      以下給出引理2和引理3。引理2說明線搜索能夠保證得到一個正數(shù)步長,使得算法1在有限步內(nèi)停止,從而說明提出的算法1是有意義的。

      引理2 若假設(shè)(1)和假設(shè)(2)成立,則MMHS算法有意義。

      證明假設(shè)不成立,或者M(jìn)LS算法不停止,那么,使得

      ‖gk‖≥η,?k∈N∪{0}。

      (13)

      下面證明滿足式(4)的步長αk存在下界。

      由式(9)和假設(shè)1的(2)有

      (14)

      由式(10)和式(12)可得

      (15)

      結(jié)合式(10)、(14)和(15),可得

      引理3 如果假設(shè)1成立,且{xk}是由MHS算法生成。設(shè)x*是式(1)的解,則有

      (17)

      成立。

      證明因為F是單調(diào)的,x*是式(1)的解,結(jié)合超平面Hk的定義,得到

      〈F(zk)-F(x*),x*-zk〉=

      〈F(zk),x*-zk〉≤0,

      (18)

      容易驗證xk+1是xk在半平面Mk={x∈Rn|〈F(zk)T,x-zk〉≤0}上的投影。如果x*處在半平面Mk空間里,根據(jù)投影算子基本性質(zhì),得到〈xk-xk+1,xk+1-x*〉≥0。則有

      由此得出式(16)成立。

      再將式(16)移項,整理得

      將上式累加,令k→+∞,推出式(17)成立。

      由式(4)和(7),可得

      聯(lián)合式(17),可得到

      因此,有

      (19)

      由引理1、引理2和引理3,結(jié)合假設(shè)1和式(19),利用反證法,可以得到算法1全局收斂性的結(jié)論。

      (20)

      成立。

      證明采用反證法。假設(shè)式(20)不成立,則存在一個常數(shù)ν>0,使

      由式(12),有

      (21)

      根據(jù)式(10)和(15)得到

      聯(lián)合式(19),可得

      當(dāng)k→∞時,對?k∈N2,上式兩邊取極限,即有

      而式(11)兩邊同取極限,得到

      顯然矛盾。所以假設(shè)不成立,即式(20)成立。證畢。

      4 數(shù)值試驗

      本節(jié)通過對算法1與經(jīng)典HS、三項HS算法在求解大規(guī)模非線性單調(diào)方程組問題上進(jìn)行數(shù)值試驗和比較分析,檢驗算法1的有效性。在算法1的步驟3中,分別使用式(22)和式(23)替代搜索方向dk,其他步驟和算法1的步驟一致,則對應(yīng)為經(jīng)典HS算法和三項HS算法,在文中分別稱之為算法2和算法3。

      其中yk=Fk+1-Fk。

      具有固定初始點(diǎn)的函數(shù)來自于文獻(xiàn)[7,14],具體的函數(shù)名稱與初始點(diǎn),如表1所示。

      表1 測試函數(shù)

      表2 數(shù)值計算結(jié)果

      續(xù)表2

      從表2可以看出,在精度相同條件下,NI、NF和CPU運(yùn)行時間3個測試指標(biāo)中,算法1最好,算法2其次,算法3最差。為直觀反映3種算法的性能差異,本文采用文獻(xiàn)[17]的曲線分析比較方法,分別作出3種算法關(guān)于NI、NF和CPU運(yùn)行時間的曲線比較圖,見圖1~3。由圖1~3可知,總體上算法1比算法2和算法3更優(yōu),魯棒性更好,是一種有效的算法。

      圖1 迭代次數(shù)比較圖

      圖2 目標(biāo)函數(shù)值計算次數(shù)比較圖

      圖3 CPU運(yùn)行時間比較圖

      5 結(jié) 論

      (1)修正的HS投影算法不僅繼承了YUAN搜索方向自動充分下降的特點(diǎn),而且還具有信賴

      域的性質(zhì),使得本文所提算法對一般函數(shù)的全局收斂性變得更為容易。

      (2)測試問題的最大維數(shù)有45 000個變量,數(shù)值計算結(jié)果表明,對給定的測試函數(shù),本文提出的算法比經(jīng)典HS方法和3項HS方法魯棒性更優(yōu)、更具有競爭力。未來將進(jìn)行更多的試驗證明所提出算法的性能,并嘗試將算法進(jìn)一步推廣到實際的大規(guī)模非線性問題。

      猜你喜歡
      共軛收斂性單調(diào)
      一個帶重啟步的改進(jìn)PRP型譜共軛梯度法
      一個改進(jìn)的WYL型三項共軛梯度法
      數(shù)列的單調(diào)性
      數(shù)列的單調(diào)性
      Lp-混合陣列的Lr收斂性
      巧用共軛妙解題
      一種自適應(yīng)Dai-Liao共軛梯度法
      對數(shù)函數(shù)單調(diào)性的應(yīng)用知多少
      END隨機(jī)變量序列Sung型加權(quán)和的矩完全收斂性
      行為ND隨機(jī)變量陣列加權(quán)和的完全收斂性
      迭部县| 财经| 壶关县| 沙坪坝区| 弋阳县| 军事| 澜沧| 乐都县| 太保市| 五大连池市| 八宿县| 石嘴山市| 聂荣县| 墨江| 长葛市| 蓬莱市| 新建县| 无棣县| 玉林市| 和静县| 甘泉县| 茶陵县| 南岸区| 上栗县| 专栏| 晋宁县| 龙口市| 巫山县| 桐乡市| 喀喇| 恩平市| 句容市| 三都| 湖北省| 滁州市| 温宿县| 栖霞市| 竹山县| 安化县| 南乐县| 封开县|