求解無約束優化問題的兩類修正的WYL共軛梯度方法

孫穎異,李健,孫中波,王增輝

(1.吉林農業大學信息技術學院,吉林 長春130118;2.長春工業大學電氣與電子工程學院,吉林 長春130012;3.東北師范大學人文學院理工學院,吉林 長春130117)

1.引言

考慮如下無約束優化模型

其中f(x) : Rn →R是連續可微函數.共軛梯度法是求解這類問題(1.1)的有效算法之一,具體迭代格式如下

其中xk是第k次迭代點,αk是搜索步長,搜索步長可以按照某類精確線搜索準則或者非精確線搜索準則條件計算得到,dk是搜索方向,可以按照如下公式進行計算

式(1.3)中gk=▽f(xk)是目標函數梯度,βk?1是共軛梯度參數.不同的參數βk?1對應不同的共軛梯度方法.例如,Fletche-Reeves (FR)法、Hestenes-Stiefel (HS)法、Polak-Ribiere-Polyak(PRP)法、Conjugate-descent(CD)法、Liu-Storey (LS)法、Dai-Yuan (DY)法[1?7].它們對應的共軛梯度參數βk如下

其中yk=gk ?gk?1,‖·‖為歐幾里得范數.在精確線搜索準則條件下,如果目標函數為二次函數,上述六類共軛梯度法是等價的.但是,如果目標函數為一般函數時,這六類算法的性質差別很大.PRP共軛梯度算法和HS共軛梯度算法是這幾類經典共軛梯度法中計算效率較好的兩類算法.由于PRP共軛梯度算法和HS共軛梯度算法的搜索方向具有很好的性質,也即是可以克服算法在迭代步驟充分大的情況下產生小步長現象.但是,在非精確線搜索準則條件下,如果目標函數是非凸函數時,PRP 共軛梯度算法和HS共軛梯度算法無法保證產生的搜索方向為下降方向,從而,影響了算法的全局收斂性.雖然經典PRP共軛梯度法收斂性很難直接給出,但是,通過對搜索方向進行適當修正,便可得到該類算法的全局收斂性[8?11].POWELL 指出共軛梯度參數βk不應該小于零,從而可以得到更加優良的共軛梯度算法.隨后,學者們提出了一系列滿足共軛梯度參數βk大于零的修正類共軛梯度法[12?13].最近,WEI等[14]提出了一個新的共軛梯度法(簡稱WYL共軛梯度法).他們定義如下形式的共軛梯度參數

在非精確線搜索條件下,證明了WYL共軛梯度法具有全局收斂性[15].為了滿足共軛梯度參數非負性,YUAN提出了一類修正的PRP共軛梯度法(MPRP方法),共軛梯度參數表達式如下

當搜索方向滿足充分下降條件時,全局收斂性分析不依賴于線搜索準則條件,因此,提高了算法的計算效率.本文首先基于MPRP方法思想,提出了一類修正的WYL共軛梯度法(簡稱為DWYL共軛梯度法).特別地,共軛梯度參數βk按照如下公式進行計算

2.DWYL共軛梯度法和MDWYL共軛梯度法

假設2.1假設水平集?={x ∈Rn|f(x)≤f(x1)}有界.

假設2.2在水平集的某個鄰域?0內,目標函數f(x)是連續可微.目標函數的梯度g滿足利普希茨條件,也即是,存在一個正常數L>0,使得

由于函數迭代序列{f(xk)}是遞減的,易知由算法2.1生成的迭代序列{xk}均包含在水平集?.另外,由算法2.1和WOLFE準則,以及{gk}有界性知,

算法2.1(DWYL共軛梯度算法)

步1 給定一些正常數?,t,ρ<σ <1,選擇一個初始點x1∈Rn,k:=0.

步2 計算搜索方向.按照如下公式計算搜索方向

其中,

步3 確定終止停止迭代條件.如果‖gk‖≤?,算法停止.否則,轉入步4.

步4 利用WOLFE線搜索準則條件確定搜索步長αk

步5 更新迭代點.令xk+1=xk+αkdk,k:=k+1,返回步2.

另外,為了便于討論算法的全局收斂性,我們對搜索方向(2.2)進一步修正,提出另一類搜索方向的計算方法,也即是,假設存在一個正常數μ>0使得如下搜索方向計算公式成立

其他計算步驟與算法2.1相同,從而得到另一類修正的WYL共軛梯度算法(簡稱為MDWYL共軛梯度法).

下面將要討論DWYL共軛梯度法和MDWYL共軛梯度法的搜索方向充分下降性.

引理2.1假設2.1和2.2成立,搜索方向按照公式(2.2)計算,搜索步長滿足WOLFE線搜索準則,則搜索方向滿足如下不等式

證當k=0時,根據算法2.1中步2,知dT1g1=?‖gk‖2,結論顯然成立.

當k >0時,分如下兩種情況討論:

取a由a2+b2≥2ab得

因此,算法2.1中搜索方向滿足充分下降性,這個性質為后續全局收斂性分析提供了便利條件.

引理2.2假設2.1和2.2成立,搜索方向按照公式(2.5)計算,搜索步長滿足WOFLE線搜索準則,則搜索方向滿足如下不等式

證證明思想與引理2.1相同,因此省略.

3.全局收斂性

引理3.1[17?18]假設2.1和2.2成立,搜索方向和搜索步長按照算法2.1和步4進行計算,則有

定理3.1假設2.1和2.2成立,迭代序列{xk}和搜索方向dk分別通過算法2.1計算得到,則存在一個常數0,使得

證根據算法2.1,分如下兩種情況討論:

情況1 當k=0時,搜索方向dk=?gk,從而=1,結論顯然成立.

情況2 當k >0時,搜索方向dk=?gk+βDWYLk?1dk?1,其中,

當gTk dk?1≤0時,搜索方向dk=?gk,從而=1,結論顯然成立.

當gTk dk?1>0時,搜索方向

定理3.2假設2.1和2.2成立,迭代序列{xk}和搜索方向dk分別通過算法2.1和公式(2.5) 計算得到,若存在一個常數ω >0,使得‖gk‖≥ω,則存在一個常數ˉ0,使得

證從(2.5)出發,分如下兩種情況討論:

1)若|gTk+1y?k|‖dk‖≥μ‖gk+1‖,則‖dk+1‖=‖gk+1‖,此時,=1,結論顯然成立.

2)若|gTk+1y?k|‖dk‖<μ‖gk+1‖,令

由上式,有

于是,由(3.4)可以估計‖dk+1‖

令

因此,結論成立.

定理3.4假設條件2.1和2.2成立,迭代序列{xk}和搜索方向dk分別通過算法2.1,則有

證假設(3.7)不成立,則存在一個常數>0,存在k ∈N 使得

由(3.2)可以得到

所以結論成立.

4.數值實驗

本文采用文[19]中的部分函數為測試函數.在Matlab7.1環境下編寫程序代碼,CPU為奔騰(R),2.19 GHz,1 Gb內存.程序代碼中的參數選取為

具體數值結果見表1-表4,表1代表本文DWYL共軛梯度算法數值結果,表2代表本文MDWL共軛梯度算法數值結果,表3代表WYL共軛梯度算法數值結果[14],表4代表修正的WYL 共軛梯度算法數值結果[15].其中P代表測試問題,N代表測試問題的變量維數,NI代表算法迭代次數,NG代表目標函數梯度計算次數,NF目標函數計算次數,CPU-TIME 代表計算機實際計算時間,s代表秒.

表1 本文DWYL共軛梯度算法數值結果

表2 本文MDWYL共軛梯度算法數值結果

表3 WYL共軛梯度算法數值結果[14]

表4 修正的WYL共軛梯度算法數值結果[15]

從表1-表2可見,本文提出的兩類算法是可行的、有效的.表3和表4是文[14-15]數值仿真結果.從迭代次數和CPU 時間來看,本文提出的算法要好于文[14-15]算法.同時,由于本文的算法產生的搜索方向具有充分下降的性質,而且算法的收斂性也獨立于線搜索準則,從而,使得算法具有較好的計算效率.另外,本文算法DWYL雖然好于文[14-15]算法,但是,通過對搜索方向的討論,我們采用(2.2)公式計算搜索方向,在不依賴于線搜索準則條件下,實現了算法的全局收斂,從而提高了算法的計算效率.從表2的數值結果可以看出,線搜索準則對收斂性分析的影響還是比較明顯.

表5 測試問題和變量維數

表6 測試問題和變量維數

圖1 基于時間性能指標的對比圖

為了進一步說明本文提出的DWYL共軛梯度算法和MDWYL共軛梯度算法適合大規模無優化問題,我們選取了CUTEr測試庫中的40個無約束優化問題,其中測試函數的維數為50000,具體見表5和表6.圖1的左側代表DWYL共軛梯度算法和MDWYL共軛梯度算法以及WYL共軛梯度算法[14]和修正的WYL共軛梯度算法[15]的運行最快速度,右側代表的是各個算法求解問題的成功率,上側代表各個算法在規定的迭代終止條件下可以求解測試庫中函數的數量.從圖1知,本文提出的兩類算法從收斂速度及CPU運行時間上均優于WYL 共軛梯度算法[14]和修正的WYL共軛梯度算法[15].因此,本文提出的兩類算法不僅擁有很好的全局收斂特性而且數值試驗效果也好于經典算法[14?15].

5.總結

本文提出了兩類修正的WYL充分下降的共軛梯度法,算法在每次迭代過程中產生的搜索方向均為充分下降方向.在水平集有界和目標函數的梯度滿足李普希茲函數連續條件下,證明了算法的全局收斂性.數值結果表明算法是可行、有效的.進一步的工作是如何把該類算法用于求解非凸優化問題是未來研究方向之一.另外,針對求解大規模的數值優化問題,把這些計算效率高的共軛梯度算法與智能優化算法相結合,充分發揮算法各自優點,提出快速收斂的混合優化算法也是未來主要研究工作.