無約束優(yōu)化問題的非單調(diào)Perry-Shanno方法

林海嬋

(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院， 海南 ?？?570228)

無約束優(yōu)化問題的非單調(diào)Perry-Shanno方法

林海嬋

(海南大學(xué) 信息科學(xué)技術(shù)學(xué)院， 海南 ?？?570228)

提出了一個(gè)處理無約束優(yōu)化問題的PS無記憶擬牛頓型方法.在一定的假設(shè)條件下,分析了算法全局收斂性，數(shù)值試驗(yàn)結(jié)果表明該算法是有效的.

無記憶擬牛頓型方法； 非單調(diào)線搜索； 全局收斂性

考慮如下的無約束優(yōu)化問題

(1)

其中，f:Rn→R是連續(xù)可微的函數(shù).

Perry-Shanno(PS)無記憶擬牛頓型方法最初由Perry[1]和Shanno[2-3]提出，具有如下的迭代形式

xk+1=xk+αkdk，

(2)

其中，αk>0是由一維線搜索得到的一個(gè)步長,而搜索方向dk滿足

d0=-g0，

(3)

其中，gk是函數(shù)f在xk處的梯度，Bk由下列Perry-Shanno修正公式

(4)

其中，sk=xk+1-xk，yk=gk+1-gk.如果采用Bk的逆形式Hk,可得到如下的修正公式

(5)

相應(yīng)的迭代方向定義如下

(6)

非單調(diào)線搜索方法首次由Grippo[4]提出.選擇步長αk滿足下列條件

(7)

(8)

盡管非單調(diào)線搜索方案(7)在某些情況下是有效的，但仍然存在一些明顯的缺陷(詳見文獻(xiàn)[13]).為了彌補(bǔ)不足,Zhang和Hager[14]提出了利用函數(shù)平均值代替(7)中的最大函數(shù)值的Wolfe型非單調(diào)線搜索技術(shù)尋找αk,使其滿足不等式

(9)

(10)

(11)

數(shù)值試驗(yàn)結(jié)果表明這種非單調(diào)技術(shù)明顯優(yōu)于傳統(tǒng)的非單調(diào)線搜索技術(shù)(7)(詳見文獻(xiàn)[14,11]).

最近，Gu和Mo[15]對Zhang和Hager提出的非單調(diào)線搜索技術(shù)(2)進(jìn)行了改進(jìn)，并給出了非單調(diào)技術(shù)

(12)

(13)

并且0≤θk≤θmax<1.數(shù)值試驗(yàn)結(jié)果表明這一改進(jìn)實(shí)用且有效[15,10].

當(dāng)目標(biāo)函數(shù)是凸函數(shù)時(shí)，PS方法的全局收斂性已取得一些研究成果.比如，帶精確線搜索的PS方法的全局收斂性已經(jīng)被Perry[1]驗(yàn)證；Shanno[2]給出了帶Wolfe線搜索的PS方法的全局收斂性證明；利用如下的線搜索方法

(14)

推廣了Shanno的結(jié)論,其中μ1和μ2是2個(gè)正常數(shù)。隨后，Liu[12]等人和Yu[8]等人分別給出了具有全局收斂性的帶非單調(diào)線搜索的PS方法.而這些方法的收斂性證明僅僅與上述提到的具體線搜索準(zhǔn)則有關(guān).需要指出的是，其對非凸優(yōu)化的PS方法的全局收斂性研究進(jìn)展不大.

受一般化線搜索準(zhǔn)則[16]的啟發(fā),筆者提出了一個(gè)具有一般形式的非單調(diào)無記憶PS方法，在一定的條件下，還證明其全局收斂性，數(shù)值實(shí)驗(yàn)結(jié)果表明該算法是有效的.

1 新的非單調(diào)線搜索模型

給出一種具有一般形式的非單調(diào)線搜索模型，因此，給出相關(guān)定義[16].

利用定義1，給出以下定義.

3)f(xk+αkdk)≤f(xk)-σ3(γk)‖dk‖.

注1 由文獻(xiàn)[16]中的定理2可知，經(jīng)典的線搜索準(zhǔn)則，比如回溯步長準(zhǔn)則、Goldstein步長準(zhǔn)則、Armijo步長準(zhǔn)則和Wolfe步長準(zhǔn)則都是定義2中的線搜索準(zhǔn)則的特殊情況.

基于以上定義和式(9)的啟發(fā)，引入了一種新的非單調(diào)線搜索準(zhǔn)則，其步長αk定義

(15)

注2 從式(12)和(13)可知，Dk是由函數(shù)值f(x0)，f(x1)，…，f(xk)構(gòu)成的一個(gè)凸組合，同時(shí)，θk的選擇控制式(15)的非單調(diào)性程度.如果θk=0，且對于任意的k有

然后式(15)就變成了具有一般形式的單調(diào)Wolfe線搜索.

結(jié)合新的線搜索準(zhǔn)則式(15)，給出如下的非單調(diào)PS無記憶擬牛頓方法：

NPS算法

步驟2計(jì)算gk，若gk≤ε，停止；否則，令dk=-Hkgk；

步驟3找出滿足式(15)的步長αk；

步驟4令xk+1=xk+αkdk；

步驟5修正Hk為Hk+1；

步驟6令k：=k+1，轉(zhuǎn)步驟2.

2 算法的收斂性分析

分析NPS算法的收斂性.為此，需如下假設(shè)：

2)f(x)是Rn上的二次連續(xù)可微函數(shù)，并且存在正常數(shù)c1和c2滿足

(16)

引理1 若假設(shè)2)滿足，則存在正常數(shù)c3，使得

(17)

(18)

證明不等式(17)的證明可參考文獻(xiàn)[12]中的引理1.因此，僅證明不等式(18).利用假設(shè)2)，可推得

(19)

結(jié)合Cauchy-Schwartz不等式，由此可得

(20)

證畢.

注3 由引理1和式(19)，容易推出

引理2 由更新公式(4)和(5)分別定義矩陣序列{Bk}和{Hk}是對稱正定的.

證明類似于文獻(xiàn)[17]中的定理5.1.5的證明方法可證.

引理3 在假設(shè)2)滿足的條件下，若存在ε>0，使得對于所有的k都有‖gk‖≥ε，那么

(21)

證明通過更新公式(4)和(5)，易推出Bk和Hk的跡滿足

(22)

結(jié)合式(20)和引理1，可推出

trace(Bk)≤nc3，

(23)

(24)

顯然，

(25)

意味著

(26)

其中

注意到

(27)

結(jié)合式(26)和(27)，則有

引理4 令{xk}是由帶準(zhǔn)則(15)的算法NPS產(chǎn)生的無限序列，若假設(shè)1)和2)滿足，則

fk≤Dk?k .

(28)

證明利用歸納法.顯然，式(28)對于k=0滿足.假設(shè)式(27)對于某個(gè)k成立，由式(13)可得

fk+1-Dk+1=θk+1(fk+1-Dk) ?k，

(29)

結(jié)合式(15)和(29)，即可推出

fk+1≤Dk+1，

(30)

即式(28)對于k+1也成立.故式(28)成立.

證明由式(13)和(15)，對于所有的k,有

Dk+1=θk+1Dk+(1-θk+1) fk+1≤θk+1Dk+(1-θk+1)Dk=Dk，

(31)

從而第一個(gè)結(jié)論成立；

f(xl+1)≤Dl+1≤Dl≤…≤D0=f(x0)，

引理6 令{xk}是由帶準(zhǔn)則(15)的算法NPS產(chǎn)生的無限序列.若假設(shè)1)和2)成立，則

(32)

(33)

由由引理4和引理5，并結(jié)合式(33)及假設(shè)1)即可推出結(jié)論(32)成立.

引理7 設(shè){xk}是由帶準(zhǔn)則(15)的算法NPS產(chǎn)生的無限序列，若假設(shè)1)和2)滿足，則

(34)

證明利用反證法.若結(jié)論(34)不成立，則存在正常數(shù)ε，使得，

‖gk‖≥ ε ?k ，

(35)

由假設(shè)2)和式(15)，可推出存在一個(gè)常量L滿足

(gk+1-gk)Tdk≤‖gk+1-gk‖‖dk‖≤αkL‖dk‖2

(36)

和

(37)

從而

(38)

結(jié)合式(38)和(21)可知

(39)

因?yàn)棣?，σ2和σ3是強(qiáng)制函數(shù)，再由定義1，式(21)，式(27)和(39)可推出存在ε1>0，ε2>0和ε3>0滿足

σ2(γk)≥ε2，

σ3(γk)‖dk‖≥ε3，

因此

(40)

其中，ε0=min{ε1，ε2，ε3}，顯然，式(40)與式(32)相矛盾.因此，結(jié)論(34)正確.

3 數(shù)值試驗(yàn)

為了驗(yàn)證NPS算法的可行性，選取了文獻(xiàn)[18]中的35個(gè)標(biāo)準(zhǔn)測試函數(shù)進(jìn)行測試，其中程序是利用MatlabR2010a進(jìn)行了編程，在測試過程中其初始參數(shù)分別選取為β1=0.01，β2=0.3，α0=1，θ=0.9.

為了檢驗(yàn)NPS算法的有效性，若第一組數(shù)值實(shí)驗(yàn)中，將其與其他經(jīng)典的PRP，HS，和DY共軛梯度法(參考文獻(xiàn)[17])進(jìn)行了比較，所有算法的終止條件均為‖gk‖≤10-5.詳細(xì)的測試結(jié)果如表1所示,其中,字母“P”為測試問題，其排列順序同文獻(xiàn)[18];n為測試函數(shù)的維數(shù).數(shù)值試驗(yàn)是以形式“k/kf”給出的,k為迭代次數(shù)，kf為函數(shù)值調(diào)用次數(shù).此外若某個(gè)測試函數(shù)在迭代5 000次后或其運(yùn)行時(shí)間超過300s后仍不能收斂到極值點(diǎn),就認(rèn)為此測試函數(shù)在該種算法下運(yùn)行失敗，記“failure”.

為了更直觀的比較5種算法的數(shù)值試驗(yàn)效果,利用表1的數(shù)值結(jié)果,并且根據(jù)文獻(xiàn)[19]中給出的關(guān)于性能線(PerformanceProfile)的定義,分別作出性能比較圖,如圖1和圖2所示.需要指出的是,由于梯度調(diào)用次數(shù)與算法的迭代次數(shù)是相同的，所以梯度調(diào)用次數(shù)的性能比較圖在此沒有給出.

表1 5種算法的數(shù)值試驗(yàn)結(jié)果

圖1 算法迭代次數(shù)比較圖 圖2 函數(shù)值調(diào)用次數(shù)比較圖

從圖1和2中可以看出，從迭代次數(shù)和函數(shù)值調(diào)用次數(shù)來看,NPS算法的表現(xiàn)性能要優(yōu)于其他4種算法.此外，從算法的失敗次數(shù)來看，NPS算法的失敗次數(shù)也少于其他4種算法.因此，NPS算法在一定程度上優(yōu)于其他4種算法.

為了檢驗(yàn)NPS算法的有效性，在第2組數(shù)值試驗(yàn)中，將其與帶不同非單調(diào)線搜索規(guī)則的NPS方法進(jìn)行了比較，這些規(guī)則分別是式(9)(記為NPS1方法)和式(8)(記為NPS2方法)，測試函數(shù)來自文獻(xiàn)[18]中18個(gè)無約束優(yōu)化問題.同時(shí)，初始參數(shù)除M=5外，其余同前.詳細(xì)的測試結(jié)果見表2，性能比較圖見圖3和圖4.

表2 3種算法的數(shù)值試驗(yàn)結(jié)果

圖3 算法迭代次數(shù)比較圖 圖4 函數(shù)值調(diào)用次數(shù)比較圖

從圖3和圖4可以看出，從迭代次數(shù)和函數(shù)值調(diào)用次數(shù)來看，NPS算法的表現(xiàn)性能要優(yōu)于其他2種算法.

5 小 結(jié)

通過理論分析和數(shù)值實(shí)驗(yàn)的結(jié)果，在處理無約束優(yōu)化問題時(shí)，NPS算法具有計(jì)算速度快，存貯容量小的優(yōu)點(diǎn).當(dāng)然，在大規(guī)模優(yōu)化問題中，NPS算法的計(jì)算速度與其他算法的計(jì)算速度相差無幾，因此，下一步的工作重點(diǎn)是如何改進(jìn)NPS算法，使其提高大規(guī)則優(yōu)化問題的計(jì)算速度.

[1]PerryJM.Aclassofconjugategradientalgorithmswithatwostepvariablemetricmemory[D].Evanston：NorthweaternUniversity，1977.

[2]ShannoDF.Ontheconvergenceofanewconjugategradientalgorithm[J].SIAMJournalonNumericalAnalysis， 1978(15): 1 247-1 257.

[3]ShannoDF.Conjugategradientmethodswithinexactsearches[J].MathematicsofOperationsResearch， 1978，3: 244-256.

[4]GrippoL，LamparielloF，LucidiS.AnonmonotonelinesearchtechniqueforNewton’smethod[J].SIAMJournalonNumericalAnalysis，1986，23:707-716.

[5]DengNY,XiaoY，ZhouFJ.Nonmonotonetrustregionalgorithm[J].JournalofOptimizationTheoryandApplications， 1993，76： 259-285.

[6]SunWY.Nonmonotonetrustregionmethodforsolvingoptimiztionproblems[J].AppliedMathematicsandComputation，2004(156)： 159-174.

[7]QuSJ,ZhangKC，YangYT.Anonmonotonetrustregionmethodofconicmodelforunconstrainedoptimization[J].JournalofComputationalandAppliedMathematics， 2008(220)：119-128.

[8]YuZS,PuDG.Anewnonmonotonelinesearchtechniqueforunconstrainedoptimization[J].JournalofComputationalandAppliedMathematics, 2008(219): 134 -144.

[9]AhookhoshM，AminiK.Anefficientnonmonotonetrust-regionmethodforunconstrainedoptimization[J].NumericalAlgorithms, 2012，59 :523-540.

[10]OuYG.AnonmonotoneODE-basedmethodforunconstrainedoptimization[J].InternationalJournalofComputerMathematics, 2014，91(8):1 840-1 860.

[11]HuangS,WanZ，ChenXH.Anewnonmonotonelinesearchtechniqueforunconstrainedoptimization[J].NumericalAlgorithms, 2015，68 :671-689.

[12]LiuGH，JingL.ConvergenceofnonmonotonePerryandShannomethodsforoptimization[J].ComputationalOptimizationandApplications,2000，16: 159-172.

[13]DaiYH.Onthenonmonotonelinesearch[J].JournalofOptimizationTheoryandApplications，2002，112(2)：315-330.

[14]ZhangHC,HagerWW.Anonmontonelinesearchtechniqueanditsapplicationstounconstrainedoptimization[J].SIAMJournalonOptimization,2004(14):1 043-1 056.

[15]GuNZ,MoJT.Incorporatingnonmonotonestrategiesintothetrustregionmethodforunconstrainedoptimization[J].ComputersandMathematicswithApplications, 2008, 55: 2 158-2 172.

[16] 韓繼業(yè),劉光輝.無約束最優(yōu)化線搜索一般模型及BFGS方法的整體收斂性[J]. 應(yīng)用數(shù)學(xué)學(xué)報(bào)， 1995(1): 112-122.

[17] 孫文瑜,袁亞湘.最優(yōu)化理論與方法[M].北京：科學(xué)出版社, 1997.

[18]MoreJ,GarbowB,HillstromK.Testingunconstrainedoptimizationsoftware[J].ACMTransactionsonMathematicalSoftware, 1981, 7: 17-41.

[19]DolanED,MoreJ.Benchmarkingoptimizationsoftwarewithperformanceproblems[J].MathematicalProgramming(SerialA), 2002, 91: 201-213.

Non Monotone Perry-Shanno Method for Unconstrained Optimization

Lin Haichan

(College of Information Science and Technology, Hainan University, Haikou 570228, China)

In our report, a memoryless PS quasi-Newton-type method for unconstrained optimization was proposed. Under reasonable assumptions, the global convergence of the proposed method is established. The numerical results indicated that the method is effective.

memoryless quasi-Newton method; non-monotone line search; global convergence

2015-03-02

海南省自然科學(xué)基金(20151002)；海南大學(xué)中西部高校提升綜合實(shí)力計(jì)劃項(xiàng)目

林海嬋(1981-),女,海南昌江人,講師,研究方向:最優(yōu)化理論與算法, E-mail: linhaichan@163.com

1004-1729(2015)04-0318-09

O 221

A DOl：10.15886/j.cnki.hdxbzkb.2015.0056