吳素花
(重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,重慶 401331)
?
一個(gè)在Armijio線搜索下全局收斂的改進(jìn)共軛梯度法
吳素花
(重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院,重慶 401331)
非線性共軛梯度方法是解大規(guī)模無(wú)約束問(wèn)題最有效的方法之一,改進(jìn)了Liu等人提出的共軛梯度算法得到MD方法,MD方法不依賴任何線搜索具有充分下降性.在Armijio型非精確線搜索下, 證明了新方法的全局收斂性.
無(wú)約束優(yōu)化問(wèn)題;共軛梯度法;Armijio線搜索;充分下降性;全局收斂性
本文主要考慮以下無(wú)約束極小問(wèn)題:
minf(x),x∈Rn
(1)
共軛梯度法是求解這類(lèi)問(wèn)題的最有效的方法之一, 其一般迭代格式為:
xk+1=xk+αkdk
(2)
(3)
其中:αk由某種線搜索確定的步長(zhǎng),gk表示f(x)在點(diǎn)xk處的梯度,參數(shù)βk稱為共軛梯度參數(shù).本文中涉及的線搜索有下列兩種:
(4)
標(biāo)準(zhǔn)沃爾夫線搜索:
(5)
其中 0<δ<σ<1. 若存在常數(shù)c>0下式成立,則稱方法具有充分下降性.
參數(shù)βk的不同取法對(duì)應(yīng)于不同的共軛梯度法,經(jīng)典的共軛梯度法有HS方法、FR方法、LS方法、CD方法、DY方法,具體的βk選取見(jiàn)文獻(xiàn)[1-8].其中PRP方法、HS方法、 LS方法的計(jì)算效果比較好, 但是理論比較差;而FR方法、CD方法、DY方法的計(jì)算效果比較差,但是理論好.為了尋求在理論及數(shù)值計(jì)算上都比較好的方法,許多學(xué)者對(duì)共軛梯度方法進(jìn)行了研究.
2005年,Hager和Zhang[9]提出了HZ方法,其中參數(shù)βk的選取如下:
(6)
其中:yk-1=gk-gk-1,sk-1=xk-xk-1.
Dai 和 Kou[10]提出了DK方法,其中參數(shù)βk的選取如下:
(7)
2015年,Liu[10]提出D方法,共軛梯度參數(shù)βk如下:
(8)
為了得到方法對(duì)一般函數(shù)的全局收斂性,文中對(duì)D方法進(jìn)行了如下的截?cái)嘈拚?/p>
下面分析liu等[11]提出的D方法.D方法的共軛梯度參數(shù)如下:
令:
Dai[12]提出了修正割線條件:Bksk-1=zk-1
(9)
用割線條件式(9)對(duì)D方法進(jìn)行修正得到MD方法,共軛參數(shù)βk取值如下:
(10)
下證MD方法的全局收斂定理.
為了證明MD方法的全局收斂性, 對(duì)目標(biāo)函數(shù)進(jìn)行一般假設(shè):
(A2) f(x)在水平集Ω的一個(gè)領(lǐng)域N內(nèi)連續(xù)可微,并且梯度gk滿足Lipschitz連續(xù),即存在常數(shù)L>0使得下式成立:
‖g(x)-g(y)‖≤L‖x-y‖,?x,y∈N .
(11)
為了證明MD方法的全局收斂性,分三步進(jìn)行:首先證明MD方法不依賴線搜索具有充分下降性;然后給出兩個(gè)引理;最后證明全局收斂定理.
(12)
證明該定理由第二部分方法的提出過(guò)程易證得.
引理1αk>0由Armijo線搜索(4),則存在一個(gè)常數(shù)c1>0,使得下式對(duì)所有k≥0都成立:
(13)
證明由Armijo線搜索以及假設(shè)(A1)-(A2)可得:
(14)
下面分兩種情況證明式(13):
2)當(dāng)αk<1時(shí),由Armijio線搜索條件可知ρ-1αk不滿足式(4),則有下式成立:
(15)
由微分中值定理以及Lipschitz條件(11)式,存在t∈(0,1)使得:
‖xk+tρ-1αkdk-xk‖‖dk‖
引理2假設(shè)(A1)~(A2)成立,αk>0由Armijo線搜索求得,βk由式(10)確立,dk由式(3)確定,則有:
(16)
證明由式(13)和式(14)可得:
由式(12)可得:
(17)
證畢.
下證MD方法對(duì)一般函數(shù)的全局收斂性.
定理2目標(biāo)函數(shù)f(x)滿足一般假設(shè)(A1)~(A2),αk由Armijo線搜索確定 ,MD方法全局收斂,即:
(18)
由上式及式(3)可得:
[1]HESTENESMR,STIEFELE.Methodsofconjugategradientsforsolvinglinearsystems[J].JournalofResearchoftheNationalBareauofStandards,1952,49:409-436.
[2]FLETCHERR,REEVESCM.Functionminimizationbyconjugategradients[J].TheComputerJournal,1964,7(2):149-154.
[3]POLAKE,RIBIEREG.Notesurlaconvergencedeméthodesdedirectionsconjuguées[J].ESAIM:MathematicalModellingandNumericalAnalysis-ModélisationMathématiqueetAnalyseNumérique,1969,3(R1):35-43.
[4]POLYAKBT.Theconjugategradientmethodinextremalproblems[J].USSRComputationalMathematicsandMathematicalPhysics,1969,9(4):94-112.
[5]FLETCHERR.PracticalMethodsofOptimizationvol.1:UnconstrainedOptimization[M].NewYork:JohnWiley&Sons,1987.
[6]LIUY,STOREYC.Efficientgeneralizedconjugategradientalgorithms,Part1:Theory[J].JournalofOptimizationTheoryandApplications,1991,69(1):129-137.
[7]DAIYH,YUANGY.Anonlinearconjugategradientmethodwithastrongglobalconvergenceproperty[J].SIAMJournalonOptimization,1999,10(1):177-182.
[8] 王勝,關(guān)洪波.一種求解單調(diào)非線性方程組的凸組合算法[J].吉首大學(xué)學(xué)報(bào)(自然科學(xué)版),2014,35(1);12-14.
[9]HAGERWW,ZHANGH.Anewconjugategradientmethodwithguaranteeddescentandanefficientlinesearch[J].SIAMJournalonOptimization,2005,16(1) :170-192.
[10]DAIYH,KOUCX.AnonlinearconjugategradientalgorithmwithanoptimalpropertyandanimprovedWolfelinesearch[J].SIAMJournalonOptimization,2013,23(1):296-320.
[11]LIUH,WANGH,QIANX,etal.Aconjugategradientmethodwithsufficientdescentproperty[J].NumericalAlgorithms,2015,70(2):269-286.
[12]DAI,ZF,FENGHW.Globalconvergenceofamodifiedhestenes-stiefelnonlinearconjugategradientmethodwitharmijolinesearch[J].NumericalAlgorithms,2012,59(1):79-93.
責(zé)任編輯:時(shí) 凌
An Improved Conjugate Gradient Method with Global Convergence Property Under the Armijio Line Search
WU Suhua
(School of Mathematics Science,Chongqing Normal University,Chongqing 401331,China)
Conjugate gradient methods are a class of important methods for solving large-scale unconstrained optimization problems.In this paper,we present a modified conjugate gradient method based on the conjugate gradient parameter of Liu et al..The new method has sufficient descent property independent of any line search.We establish the convergence results of the algorithms under the Armijio line search conditions.
unconstrained optimization;conjugate gradient method;Armijio line search;suffcient descent property;global convergence
2016-07-16.
吳素花(1991- ),女(苗族),碩士生,主要從事最優(yōu)化理論和算法研究.
1008-8423(2016)04-0394-04
10.13501/j.cnki.42-1569/n.2016.12.008
O224
A