焦佳佳

(重慶師范大學(xué)數(shù)學(xué)學(xué)院，重慶401331)

?

一個修正的三項LS 共軛梯度法

焦佳佳

(重慶師范大學(xué)數(shù)學(xué)學(xué)院，重慶401331)

摘要:基于已有的共軛梯度法的思想，提出了一個三項LS共軛梯度方法，該方法能保證搜索方向在不需要任何線搜索下具有充分下降性，并在適當(dāng)條件下獲得此方法對一般函數(shù)的全局收斂性．

關(guān)鍵詞:共軛梯度法;充分下降性;全局收斂性

1基礎(chǔ)知識

考慮無約束優(yōu)化問題:

其中f: Rn→R是連續(xù)可微函數(shù)．共軛梯度法是求解大規(guī)模無約束優(yōu)化問題( 1)的一種有效方法，其迭代格式如下:

其中g(shù)k=f( xk)，dk是搜索方向，k是用某線搜索得到的步長，k是參數(shù)．不同的參數(shù)表達(dá)式k對應(yīng)著不同的共軛梯度法，著名的有FkR，PkRP，HkS等．常用的線搜索有Wolfe線搜索、強(qiáng)Wolfe線搜索、Armijo-type線搜索等，其中Wolfe線搜索要求k滿足

與其他共軛梯度法相比，PRP方法的數(shù)值表現(xiàn)是目前認(rèn)為最好的方法之一，但該方法的收斂性不理想．研究發(fā)現(xiàn)，PRP方法收斂性不好的另一個原因在于它不具有充分下降性．充分下降性是指對所有的k，式( 7)成立:

其中c為常數(shù)，此性質(zhì)在收斂性分析中起著非常重要的作用．因此，許多學(xué)者都希望找到數(shù)值表現(xiàn)可與PRP相媲美同時性質(zhì)又比其好的方法．

Yu，Guan和Li在文獻(xiàn)［4］中提出了具有充分下降性的修正PRP方法，其公式為

Zhang等在文獻(xiàn)［5］中給出一個三項的PRP共軛梯度法，其方向定義為

與三項PRP方法類似，具有充分下降性的三項LS公式定義為

此方法僅僅利用了梯度值信息，忽略了函數(shù)值信息．文獻(xiàn)［6］中給出了新的擬牛頓方程:

此擬牛頓方程同時含有函數(shù)值信息和梯度值信息，且比原擬牛頓方法具有更好的收斂性和數(shù)值表現(xiàn)．受此啟發(fā)，此處給出一個三項LS共軛梯度方法，其方向定義為

2算法及其全局收斂性分析

為表述需要，稱修正的三項LS共軛梯度算法為MMLS算法，其步驟如下: 步0:給出初值x1Rn，≥0，令d1=－g1，k=1;

步1:若g1≤，則停止，否則轉(zhuǎn)步2;

步3:令xk+1=xk+kdk，gk+1=g( xk+1)，若gk+1≤，則停止，否則轉(zhuǎn)步4;

步5:令k=k+1，轉(zhuǎn)步2．

為了討論新方法的全局收斂性，假定目標(biāo)函數(shù)滿足如下基本假設(shè):

成立．

引理1對k≥0，三項LS公式的搜索方向滿足

證明如果k=0，則gT0d0=－‖g0‖2，那么式( 15)成立．當(dāng)k≥1時，利用新方向的定義可得

證畢．

則存在一個常數(shù)M＞0，使得

根據(jù)dk的定義，由式( 13) ( 14) ( 16)和( 18)可得

由式( 6)和假設(shè)( A)知

因此，對所有的k≥k0，由式( 19)和( 21)有

定理1假設(shè)( A)和假設(shè)( B)成立，dk由式( 11)確定，k由Armijo-type線搜索獲得，則gk=0．

由中值定理，引理( 2)，式( 13)和( 15)，存在hk( 0，1)，使得

3結(jié)論

對于求解大規(guī)模無約束優(yōu)化問題，給出了一種修正的三項LS共軛梯度法，該方法不依賴任何線搜索，具有充分下降性，并且在Armijo－type線搜索下證明了該方法的全局收斂性．

參考文獻(xiàn):

［1］ANDREI N．A Dai-Yuan Conjugate Gradient Algorithm with Sufficient Descent and Conjugacy Conditions for Unconstrained Optimization［J］．Applied Mathematics Letters，2008，21( 2) : 165-171

［2］LIU Y，STOREY C．Efficient Generalized Conjugate Gradient Algorithms，Part 1: Theory［J］．Journal of Optimization Theory and Applications，1991，69( 1) : 129-137

［3］GILBERT J C，NOCEDAL J．Global Convergence Properties of Conjugate Gradient Methods for Optimization［J］．SIAM Journal on Optimization，1992，2( 1) : 21-42

［4］YU G，GUAN L，LI G．Global Convergence of Modified Polak-Ribiere-Polyak Conjugate Gradient Methods with Sufficient Descent Property［J］．Journal of Industrialand Management Optimization，2008( 4) : 565-579

［5］ZHANG L，ZHOU W，LI D H．A Descent Modified Polak-Ribière-Polyak Conjugate Gradient Method and Its Global Convergence ［J］．IMA Journal of Numerical Analysis，2006，26( 4) : 629-640

［6］LI D H，F(xiàn)UKUSHIMA M．A Modified BFGS Method and Its Global Convergence in Nonconvex Minimization［J］．Journal of Computational and Applied Mathematics，2001( 1) : 15-35

［7］NARUSHINMA Y，YABE H，F(xiàn)IORD J A．A Three-term Conjugate Gradient Method with Sufficient Descent Property for Unconstrained Optimization［J］．SIAM Journal on Optimization，2011，21( 1) : 212-230

A Modified Three-term LS Conjugate Gradient mMethod

JIAO Jia-jia

( College of Mathematics Science，Chongqing Normal University，Chongqing 401331，China)

Abstract:Based on the existent ideas of the conjugate gradient method，this paper proposes a three-term LS conjugate gradient method．The presented method can make the search direction with sufficient descent property without any line search．Under certain mild conditions，global convergence is obtained．

Key words:Three-term Conjugate Gradient Method; sufficient descent property; global convergence

作者簡介:焦佳佳( 1988-)，女，陜西銅川人，碩士研究生，從事最優(yōu)化方法及其應(yīng)用研究．

收稿日期:2014－08－10;修回日期: 2014－10－08．

doi:10．16055/j．issn．1672－058X．2015．0005．004

中圖分類號:O224

文獻(xiàn)標(biāo)識碼:A

文章編號:1672－058X( 2015) 05－0013－04