陳貞晶

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

引 言

共軛梯度法是求解大規(guī)模無約束優(yōu)化問題的最經(jīng)典、最有效的方法之一,具有低存儲要求、強收斂性、計算簡單等優(yōu)點。

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

minf(x),x∈Rn

(1)

其中f:Rn→R是連續(xù)可微的。

共軛梯度法的迭代格式如下：

xk+1=xk+αkdk

(2)

d1=-g1,dk+1=-gk+1+βkdk

(3)

其中αk>0是通過某種線搜索獲得的步長，dk+1是搜索方向，gk+1=g(xk+1)是目標函數(shù)f(x)在xk+1處的梯度，βk是共軛梯度法參數(shù)，簡稱CG參數(shù)，不同的βk值對應不同的共軛梯度方法[1]。

常用的線搜索有很多，本文只考慮Wolfe線搜索(4)-(5)和強Wolfe線搜索(4)-(6)，如下所示：

f(xk+αkdk)-f(xk)≤δαk▽f(xk)Tdk

(4)

▽f(xk+αkdk)Tdk≥σ▽f(xk)Tdk

(5)

|▽f(xk+αkdk)Tdk|≤-σ▽f(xk)Tdk

(6)

共軛條件如下所示：

(7)

(8)

簡稱為DL方法且在Wolfe線搜索下滿足DL共軛條件(7)，但是不滿足充分下降條件

(9)

2005年，Hager和Zhang[4]提出了一種在任何線搜索下滿足充分下降條件的DL類型的共軛梯度方法，簡稱HZ方法，如下所示：

為了得到更好的收斂性，對HZ進行非負限制，得到如下截斷形式：

2011年，Narushima[5]等人提出了一類三項共軛梯度法的搜索方向的一般形式，如下所示：

(10)

2013年，Dai和Kou[6]在2013年提出一個共軛參數(shù)：

以及截斷形式：

這也是一個DL類型的共軛梯度法，滿足充分下降條件，是目前經(jīng)典的共軛梯度方法中計算性能最佳的方法。

這個方法簡稱為DDL方法，在Wolfe條件下滿足充分下降條件(9)，并且對一致凸函數(shù)全局收斂，在計算上與HZ、DK、DL方法作比較，結果均優(yōu)于HZ、DK、DL方法，故DDL方法有效可行。

基于上述方法的優(yōu)缺點，對以下兩種修正的DL方法做進一步的修正，使得數(shù)值結果更加理想可行。

1 修正MDL+的方法

2017年，Narushima[8]等人對無約束優(yōu)化問題，基于割線方程提出了下降的三項共軛梯度法。搜索方向和CG參數(shù)如下所示：

(11)

將其代入DL共軛條件(7)式可得出新的CG參數(shù)如下：

(12)

其中，

為了避免(12)式的分母為0，修正它為如下的形式：

(13)

其中，ξk是一個參數(shù)，定義如下:

(14)

(15)

其中，

(16)

(17)

(18)

因此，搜索方向可以表示成三項CG方法的形式，如下：

(19)

式(19)還可以寫成以下三項CG形式：

(20)

其中，

(21)

基于文獻[8]和[9]的思想，對文獻[9]中的參數(shù)ηk運用文獻[8]中的截斷形式加以截斷，提出以下兩種截斷形式，因此式(20)可以修正成以下形式：

(22)

其中，

(23)

(24)

(25)

其中，

(26)

(27)

TMDL1+算法[9]：

Step2計算αk使得Wolfe條件(4)-(5)成立；

Step5令k:=k+1,轉(zhuǎn)至Step2。

2 收斂性

接下來，研究TMDL1+算法的收斂性質(zhì)。假設gk≠0,否則將會發(fā)現(xiàn)一個平穩(wěn)點。為了證明TMDL1+方法全局收斂，對目標函數(shù)作以下兩個基本假設[12]：

假設A：

(i)f在水平集Γ={x∈Rn：f(x)≤f(x1)}上是有界的，即存在一個數(shù)B>0,使得

(28)

(ii)在Γ的某些鄰域Ω中，f(x)是連續(xù)可微的且梯度g(x)是Lipschitz連續(xù)的，即存在L>0,使得

(29)

(30)

引理1(充分下降性)[6]

(31)

成立。

證明當k=0時，d1=-g1。因此不等式(31)恒成立。當k≥1時，dk+1與gk+1做內(nèi)積可得：

(32)

引理2

假設目標函數(shù)滿足假設A，如果步長αk滿足Wolfe條件(4)-(5)，則有

(33)

接下來給出的引理3表明上述的TMDL1+算法滿足Zoutendijk條件[10]。

引理3

假設序列{dk}由(22)產(chǎn)生，其中參數(shù)tk如(24)所示，步長αk滿足Wolfe條件(4)-(5)，若f(x)滿足假設A，則有Zoutendijk條件成立：

(34)

Nocedal[11]建立的以下研究結果對證明共軛梯度法的全局收斂性具有重要作用。

引理4

假設條件A對目標函數(shù)成立，考慮共軛梯度方法(2)，其中dk是下降方,步長αk滿足強Wolfe條件(4)和(5)。如果

(35)

則有

(36)

對一致凸函數(shù)，我們可以證明TMDL1+算法收斂，即(36)成立。

定理5

假設目標函數(shù)f(x)滿足假設條件A，如果函數(shù)f(x)是一致凸的，TMDL1+算法收斂，即(36)成立。

證明：

(37)

基于(24)式可知

(38)

(39)

由方程(34)可得

成立。在引理4的基礎上，可得：

3 數(shù)值分析

Hager和Zhang[4]在2005年提出了一個具有充分下降性的共軛梯度方法，簡稱HZ方法，參數(shù)如下：

以及截斷形式：

Dai和Kou[6]在2013年提出一個共軛參數(shù)：

以及截斷形式：

圖1～圖4分別對應的是HZ+、MDL+、TMDL1+、TMDL2+這四種方法解決測試問題所用的計算時間，迭代次數(shù)，函數(shù)值計算次數(shù)，梯度值計算次數(shù)的Dolan and More性能曲線圖。從表1中可知數(shù)值越小，計算效果就越好，由此可以看出在計算時間上TMDL1+和TMDL2+方法優(yōu)于HZ+、DK+和MDL+方法。

解決測試問題所用的計算時間，迭代次數(shù)，函數(shù)計算次數(shù)，梯度計算次數(shù)結果見表1。

表1 測試結果

解決測試問題所用的計算時間，迭代次數(shù)，函數(shù)值計算次數(shù)，梯度計算次數(shù)的Dolan and More[13]性能曲線圖如圖1～圖4所示：

圖1 計算時間

圖2 迭代次數(shù)

圖3 函數(shù)計算次數(shù)

圖4 梯度計算次數(shù)

因此，通過以上的表1和圖1～圖4可知TMDL1+和TMDL2+方法在計算時間上優(yōu)于HZ+，DK+和MDL+方法，故我們的方法是有效可行的。

4 結束語

通過對三項的MDL+方法，利用HZ和DK方法的截斷形式的優(yōu)點和3TCG方法的截斷思想，提出了MDL+方法的兩種新的截斷形式，簡稱TMDL1+和TMDL2+方法，全局收斂性與MDL+方法一致。研究表明，TMDL1+和TMDL2+方法在計算效果上優(yōu)于MDL+方法和HZ+方法，是有效可行的。