一個新的修正HS共軛梯度法及全局收斂性

陳鳳華，李雙安，程慧燕

（河南理工大學(xué) 萬方科技學(xué)院，河南 鄭州 451400）

一個新的修正HS共軛梯度法及全局收斂性

陳鳳華，李雙安，程慧燕

（河南理工大學(xué) 萬方科技學(xué)院，河南 鄭州 451400）

提出了一個新的修正HS共軛梯度算法解決無約束優(yōu)化問題，該算法的特點(diǎn)是，搜索方向總是目標(biāo)函數(shù)的下降方向，且不依賴于使用何種線搜索；特別是，若使用精確線搜索，該算法退化成標(biāo)準(zhǔn)的HS共軛梯度法.且在適當(dāng)?shù)募僭O(shè)條件下，證明了文章提出的算法具有全局收斂性，最后數(shù)值實(shí)驗(yàn)表明，文章提出的算法是可行的.

無約束優(yōu)化；修正HS共軛梯度法；Wolfe線搜索；全局收斂性；數(shù)值實(shí)驗(yàn)

共軛梯度法是解決大規(guī)模無約束優(yōu)化問題的有效方法，至今對共軛梯度優(yōu)化算法各種新的變形的研究仍然很活躍，其原因是它既能克服最速下降法迭代過程中產(chǎn)生的鋸齒現(xiàn)象，又能避免牛頓法在求Hessian矩陣及其逆矩陣時(shí)的困難，它具有運(yùn)算簡便和占用存儲空間少的優(yōu)點(diǎn)，在經(jīng)濟(jì)、管理和工程計(jì)算等方面有著廣泛的應(yīng)用，相關(guān)研究見文獻(xiàn)[1-7].

本文考慮如下優(yōu)化問題：

其中f∶Rn→R為連續(xù)可微函數(shù).

求解問題（1）的共軛梯度法的迭代公式為：

其中αk>0為搜索步長，dk為搜索方向，gk=g（xk），βk為參數(shù).

共軛梯度法的關(guān)鍵是參數(shù)βk的選取，常用的βk公式有如下幾種：

其中yk-1=gk-gk-1.

文獻(xiàn)[8-9]對βk的構(gòu)造及算法的收斂性做了大量的研究.文獻(xiàn)[9]指出，PRP，HS方法在數(shù)值計(jì)算中有很好的表現(xiàn)，但是即使使用精確線搜索PRP方法也不會有全局收斂性.FR，DY方法則具有較好的收斂性質(zhì).為尋求兼具良好收斂性和優(yōu)秀數(shù)值結(jié)果的算法，許多研究者在經(jīng)典共軛梯度法的基礎(chǔ)上推出新的βk公式.

本文提出一個新的修正HS共軛梯度法，優(yōu)點(diǎn)是：

（i）由修正HS共軛梯度法產(chǎn)生的方向總是目標(biāo)函數(shù)的下降方向，且不依賴于使用何種線搜索；

（ii）若使用精確線搜索，則修正HS共軛梯度法退化成標(biāo)準(zhǔn)的HS共軛梯度法；

（iii）本文定理3.3中的條件比文獻(xiàn)[1]中的一致凸條件弱.

在一些適當(dāng)?shù)募僭O(shè)條件下，證明本文提出的算法具有全局收斂性，且數(shù)值實(shí)驗(yàn)表明本文的算法具有較好的數(shù)值結(jié)果.

1 新的修正HS共軛梯度法

受文獻(xiàn)[10]的啟發(fā)，改進(jìn)（3）中的搜索方向，構(gòu)造如下搜索方向：

對任一線搜索有：

這表明搜索方向dk是目標(biāo)函數(shù)的下降方向，若使用精確線搜索，有dk-1=0，即θk=0，則本文提出的修正HS共軛梯度法退化成標(biāo)準(zhǔn)的HS共軛梯度法.

概括上述討論，顯然有下面的定理：

定理1 搜索方向dk由（4）式定義，則在任何線搜索下，dk是f（x）在xk處的下降方向.進(jìn)一步，若使用精確線搜索，則dk與標(biāo)準(zhǔn)的HS共軛梯度法產(chǎn)生的方向相同.

基于定理1，提出一個新的修正HS共軛梯度法.算法1 新的修正HS共軛梯度法（MHSCG）

步0：初始點(diǎn) x0∈Rn，參數(shù)0<μ1<μ2<1，誤差限0<ε<1，令k=0；

步1：若‖‖

gk≤ε，算法停止；否則轉(zhuǎn)下一步；

步2：計(jì)算（4）式定義的搜索方向dk；

步3：計(jì)算步長αk：

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

步5：循環(huán)k?k+1.令，轉(zhuǎn)步1.

2 全局收斂性分析

為證明算法1具有全局收斂性，先作如下基本假設(shè).

H1水平集Ω={x0∈Rn|f (x)≤f(x0)}有界.

H2在Ω的某鄰域N內(nèi)，f（x）連續(xù)可微，且其梯度g（x）是Lipchitz連續(xù)的，即存在一常數(shù)L>0使得

由假設(shè)H1、H2知，存在一常數(shù)M>0滿足

[1]、文獻(xiàn)[10]，有如下兩個引理.

引理1[10]若假設(shè)條件H1、H2成立，則算法是良定的.

引理2[1]若假設(shè)條件H1、H2成立，對任一共軛梯度法的迭代形式（2），其中dk滿足dk<0且αk滿足Wolfe條件（6）和（7），則

式（11）結(jié)合式（5）有

定理2 如果假設(shè)H1、H2成立，在新的修正HS共軛梯度法下產(chǎn)生一無窮序列，若存在一常數(shù)滿足

由（10）知，存在一常數(shù)ρ∈(0,1)，存在一正整數(shù)k，使得當(dāng)k≥k0有

因此，對?k>k0有

3 數(shù)值實(shí)驗(yàn)

為進(jìn)一步從數(shù)值計(jì)算的角度分析算法的可行性，通過Matlab編程將算法進(jìn)行數(shù)值實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明本文提出的新的修正HS共軛梯度法是可行的.

問題1的實(shí)驗(yàn)結(jié)果見表1.

表1 問題1的數(shù)值實(shí)驗(yàn)結(jié)果Tab.1 Numerical results for question 1

問題1的實(shí)驗(yàn)結(jié)果見表1.

表2 問題2的數(shù)值實(shí)驗(yàn)結(jié)果Tab.2 Numerical results for question 2

表3 問題3-9的數(shù)值實(shí)驗(yàn)結(jié)果Tab.3 Numerical results for question 3-9

4 結(jié)論

本文提出了一個新的修正HS共軛梯度算法，該算法的特點(diǎn)是：搜索方向總是目標(biāo)函數(shù)的下降方向，且不依賴于使用何種線搜索；若使用精確線搜索，該算法退化成標(biāo)準(zhǔn)的HS共軛梯度法；定理2中的條件比文獻(xiàn)[1]中一致凸條件弱.

在適當(dāng)?shù)募僭O(shè)條件下，本文證明了提出的新的修正HS共軛梯度法具有全局收斂性，最后數(shù)值實(shí)驗(yàn)結(jié)果表明提出的算法是可行的.

參考文獻(xiàn)：

[1]Ioannis E,Livieris,Panagiotis Pintelas.Globally convergent modified Perry's conjugate gradient method[J].Applied Mathematics and Computation,2012,218:9197-9207.

[2]Shi Z J.Restricted PR conjugate gradient method and its global convergence[J].Adv Math,2002,31(1):47-55.

[3]Shi Z J.Convergence of PRP method with new non-mono?tone line search[J].Applied Mathematics and Computation, 2006,181:423-431.

[4]景書杰,鄧濤.精確搜索下具有充分下降性的混合共軛梯度法[J].河南理工大學(xué)學(xué)報(bào):自然科學(xué)版,2010,29(2):266-270．

[5]景書杰,趙海燕,鄧濤.修正的共軛梯度法在兩種線搜索下的全局收斂性[J].河南理工大學(xué)學(xué)報(bào):自然科學(xué)版,2012, 31(3):364-368．

[6]黃海.Wolfe線搜索充分下降的修正DY共軛梯度法[J].河南理工大學(xué)學(xué)報(bào):自然科學(xué)版,2013,32(3):368-372．

[7]李敏,陳宇,屈愛平.一種充分下降的DY共軛梯度法及其收斂性[J].山東大學(xué)學(xué)報(bào):理學(xué)版,2011,46(7):101-106.

[8]AL BAALI M.Descent property and global convergence of the Fletcher-Reeves method with inexact line search[J]. IMA Journal of Numerical Analysis,1985,5(1):121-124.

[9]POWELL M J D.No-convex minimization calculations and the conjugate gradient method[C].Lecture Notes in Mathematics:Vol 1066.Berlin:Springer-Verlag,1984:122-141.

[10]Zhang L,Zhou W,Li D.A descent modified PRP conju?gate gradient method and its global convergent[J].IMA Journal of Numerical Analysis,2006,26:629-640.

[11]房明磊,張聰,陳鳳華.一種新的Wolfe線搜索技術(shù)及全局收斂性[J].桂林電子科技大學(xué)學(xué)報(bào),2008,28(1):62-65.

[12]陳鳳華,張聰,房明磊.曲線搜索下的新的記憶擬牛頓法[J].廣西科學(xué),2008,15(3):254-256.

責(zé)任編輯：畢和平

A New Modified HS Conjugate Gradient Method and the Global Convergence

CHEN Fenghua，LI Shuangan，CHEN Huiyan
（Wanfang Institute of Science and Technology，Henan Polytechnic University，Zhengzhou451400，China）

In this paper,we propose a new modified HS conjugate gradient method for unconstrained optimization.An at?tractive property of the proposed method is that the direction generated by the method is always a descent direction for the ob?jective function.This property is independent of the line search used.In particular,exact line search is used,the method re?duces to the standard HS conjugate gradient method.Under appropriate conditions,we show that the new modified HS conju?gate gradient method with Wolfe line search is globally convergent.Numerical experiments show that the proposed algorithm is effective.

unconstrained optimization；modified HS conjugate gradient method；Wolfe line search；global convergence；numerical experiments

O 224

：A

：1674-4942（2015）01-0001-04

2014-10-29

國家自然科學(xué)基金（11361018）；廣西杰出青年基金（2012GXSFFA060003）；河南省教育廳科學(xué)技術(shù)研究重點(diǎn)項(xiàng)目（12B110011）