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

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

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

1.引言

考慮如下無約束優(yōu)化模型

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

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

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

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

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

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

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

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

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

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

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

步1 給定一些正常數(shù)?,t,ρ<σ <1,選擇一個(gè)初始點(diǎn)x1∈Rn,k:=0.

步2 計(jì)算搜索方向.按照如下公式計(jì)算搜索方向

其中,

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

步4 利用WOLFE線搜索準(zhǔn)則條件確定搜索步長αk

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

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

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

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

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

證當(dāng)k=0時(shí),根據(jù)算法2.1中步2,知dT1g1=?‖gk‖2,結(jié)論顯然成立.

當(dāng)k >0時(shí),分如下兩種情況討論:

取a由a2+b2≥2ab得

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

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

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

3.全局收斂性

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

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

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

情況1 當(dāng)k=0時(shí),搜索方向dk=?gk,從而=1,結(jié)論顯然成立.

情況2 當(dāng)k >0時(shí),搜索方向dk=?gk+βDWYLk?1dk?1,其中,

當(dāng)gTk dk?1≤0時(shí),搜索方向dk=?gk,從而=1,結(jié)論顯然成立.

當(dāng)gTk dk?1>0時(shí),搜索方向

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

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

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

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

由上式,有

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

令

因此,結(jié)論成立.

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

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

由(3.2)可以得到

所以結(jié)論成立.

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

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

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

表1 本文DWYL共軛梯度算法數(shù)值結(jié)果

表2 本文MDWYL共軛梯度算法數(shù)值結(jié)果

表3 WYL共軛梯度算法數(shù)值結(jié)果[14]

表4 修正的WYL共軛梯度算法數(shù)值結(jié)果[15]

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

表5 測試問題和變量維數(shù)

表6 測試問題和變量維數(shù)

圖1 基于時(shí)間性能指標(biāo)的對(duì)比圖

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

5.總結(jié)

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