吳 素 花

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

一個修正的NVPRP方法

吳 素 花

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

非線性共軛梯度方法是解決大規(guī)模無約束問題最有效的方法之一，提出了一類新的修正共軛梯度算法，新算法推廣了黃海東等的共軛梯度參數(shù)算法,不依賴任何線搜索且具有充分下降性；然后,在標準 Wolfe非精確線搜索下,得到了新算法的全局收斂性.

無約束優(yōu)化問題;共軛梯度法;充分下降性;全局收斂性

0 引 言

考慮以下無約束極小問題:

minf(x)x∈Rn

(1)

共軛梯度法是求解這類問題的最有效的方法之一,其一般迭代格式為

xk+1=xk+αkdk

(2)

(3)

其中αk為由某種線搜索確定的步長，gk表示f(x)在點xk處的梯度,參數(shù)βk稱為共軛梯度參數(shù),關(guān)于參數(shù)βk的不同取法對應(yīng)于不同的共軛梯度法.著名的共軛梯度法有1952年Hestenes和Stiefel在文獻[1]提出的HS方法；1964年Fletcher和Reevse在文獻[2]提出的FR方法；1969年P(guān)olak和Ribiere,Polyak在文獻[3-4]獨立提出的PRP方法；1987年Fletcher在文獻[5]中提出的CD方法；1991年Liu和Storey在文獻[6]中提出的LS方法； 1999年戴彧虹和袁亞湘在文獻[7]提出的DY方法，其對應(yīng)的βk的計算公式如下：

在以上經(jīng)典的βk公式的選取中，PRP，HS， LS的計算效果比較好,但是理論比較差. 對于一般的非線性函數(shù),Powell[8]舉出了一個三維的例子證明了即使采用精確線搜索,PRP方法也不收斂.為了得到好的理論及數(shù)值效果,Huang,Li和Wei[9]對PRP方法進行了修正,稱為NVPRP方法,βk由下面公式確定：

(4)

江羨珍等在文獻[10]中對PRP和HS提出了修正,βk選取如下:

(5)

(6)

基于以上βk的選取,黎小林在文獻[11]提出了:

(7)

此處將NVPRP修正如下：

(8)

(9)

其中θ>1,t>1. 記由式(2)(3)(8)確定的方法為MVNPRP方法.

為了得到新方法的全局收斂性,對目標函數(shù)進行一般假設(shè):

此處用標準沃爾夫線搜索：

(10)

其中 0<δ<σ<1. 若式(11)成立,則稱方法具有充分下降性.

(11)

引理1 對所有θ>2,若gk≠0,對于新方法MNVPRP，總有式(12)成立：

(12)

并且βk≥0.

(13)

由式(13)和式(3)可得：

≤

證畢.

引理1說明新方法不依賴線搜索具有充分下降性,下證新方法具有性質(zhì)1.

性質(zhì)1 考慮由式(2)(3)和式(8)構(gòu)成的迭代,假設(shè)

(14)

(15)

成立，則稱方法具有性質(zhì)1.

引理2 假設(shè)(A1)(A2)成立,由式(2)(3)和式(8)確定的方法在任何線搜索下都具有性質(zhì)1.

證明 由式(8)和式(13)易得：

0≤βk=

證畢.

因此，由引理1,引理2和文獻[12]中定理3.3.3即可得MNVPRP方法的全局收斂性.

定理1 目標函數(shù)f(x)滿足一般假設(shè)(A1)(A2),迭代序列由式(2)(3)產(chǎn)生，αk滿足式(10)(11),βk由式(8)確定,則MNVPRP方法全局收斂,即

(16)

同理可證明MNVPRP*方法的全局收斂性.

[1] HESTENES M R,STIEFEL E. Method of Conjugate Gradient for Solving Linear Equations[J].J Res Nat Bur Stand,1952(49):409-436

[2] FLETCHER R,REEVES C M. Function Minimization by Conjugate Gradients[J].The Computer Journal,1964,7(2):149-154

[3] POLAK E,RIBIERE G. Note Sur La Convergence De MéThodes De Directions ConjuguéEs[J].ESAIM:Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique,1969,3(R1):35-43

[4] POLYAK B T. The Conjugate Gradient Method in Extremal Problems[J].USSR Computational Mathematics and Mathematical Physics,1969,9(4):94-112

[5] FLETCHER R.Practical Methods of Optimization Vol 1:Unconstrained Optimization[M].New York:John Wiley & Sons,1987

[6] LIU Y,STOREY C. Efficient Generalized Conjugate Gradient Algorithms,Part 1:Theory[J].Journal of Optimization Theory and Applications,1991,69(1):129-137

[7] DAI Y H,YUAN Y. A Nonlinear Conjugate Gradient Method with a Strong Global Convergence Property[J].SIAM Journal on Optimization,1999,10(1):177-182

[8] POWELL M J D. Ncoconvex Minimization Calcalations and the Conjugate Gradient Method[C]∥IN:lecture Notes in Mathematics. Berlin:Springer-verlag,1984

[9] HUANG H D,LI Y J,WEI Z X. Global Convergence of a Modified Prp Conjugate Gradient Method[J].Journal of Mathematical Research Exposition，2010,30(1):141-148

[10] 江羨珍，簡金寶，馬國棟.具有充分下降性的兩個共軛梯度法[J].數(shù)學(xué)學(xué)報,2014,57(2):365-372

JIANG X Z,JIAN J B,MA G D.Two Conjugate Gradient Methods with Suffient Descent Property[J].Acta Mathematica Sinica,2014,57(2):365-372

[11] 黎小林.基于Wei-Yao-Liu共軛梯度參數(shù)的修正共軛梯度算法[D].重慶：重慶師范大學(xué)，2015

LI X L.Conjugate Gradient Algorithms Based on the Conjugate Gradient Parameter of Wei-Yao-Liu[D].Chongqing:Chongqing Normal University，2015

[12]DAI Y H,YUAN Y X. Nonlinear Conjugate Gradient Methods(in chinese)[M].Shanghai:Shanghai Scientific and Technical Publishers,2000

[13] 吳雙江.帶有最優(yōu)參數(shù)選取的修正DL共軛梯度法[J].重慶工商大學(xué)學(xué)報(自然科學(xué)版),2015，32(8)：6-9

WU S J.The Modified DL Conjugate Gradient Method with Optimal Parameter Choices[J].Journal of Chongqing Technology and Business University (Naturnal Science Edition),2015，32(8)：6-9

責(zé)任編輯：李翠薇

An Improved NVPRP Method

WU Su-hua

(School of Mathematical Science, Chongqing Normal University, Chongqing 401331, China)

Nonlinear conjugate gradient method is one of the most effective methods to solve large-scale unconstrained problems. This paper presents a class of modified conjugate gradient algorithms. The new algorithm generalizes the conjugate gradient parameter algorithm of Huang Haidong et al, and has sufficient descent property without depending on any line search. Then, under Wolfe non-accurate line search, the global convergence of the new algorithm is obtained.

unconstrained optimization; conjugate gradient algorithm; sufficient descent property; global convergence

2016-03-12；

2016-04-06.

吳素花(1991-)，女，重慶秀山人，碩士研究生，從事最優(yōu)化理論和算法研究．

10.16055/j.issn.1672-058X.2017.0002.007

O225

A

1672-058X(2017)02-0031-03