帶有循環(huán)策略的自適應(yīng)截?cái)郆B梯度法研究

楊奕涵

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

0 引言

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

(1)

其中,目標(biāo)函數(shù)f：Rn→R是連續(xù)可微的,求解問題(1)的方法主要有信賴域方法與線搜索方法,其中線搜索方法包括梯度法、共軛梯度法、牛頓法及擬牛頓法等。梯度法是最簡單、最直接的迭代方法,以負(fù)梯度作為搜索方向,其迭代格式為：

xk+1=xk-αkgk

(2)

其中,xk是當(dāng)前點(diǎn),gk?g(xk)=?f(xk)是目標(biāo)函數(shù)f(x)在xk處的梯度,αk為步長。

最早的梯度法是Cauchy[1]于1847年提出的最速下降法(SD法),采用精確線搜索步長,步長為：

(3)

其中,sk-1=xk-xk-1,yk-1=gk-gk-1,得到兩個(gè)步長公式為：

當(dāng)f(x)為二維嚴(yán)格凸二次函數(shù)時(shí),Barzilai與Borwein證明了BB法具有R-超線性收斂速度。BB法的提出極大地激發(fā)了人們對(duì)梯度法研究的熱情。1993年,Raydan[3]證明當(dāng)f(x)為任意維嚴(yán)格凸二次函數(shù)時(shí),BB法是全局收斂的。Dai和Liao[4]進(jìn)一步證明了BB法具有R-線性收斂速度。眾多學(xué)者從不同角度推導(dǎo)了不同類型的步長,提出了一些修正的BB法,如文獻(xiàn)[5-8]等。如果f(x)不是二次函數(shù),BB法可能不收斂[9]。為保證其收斂性,Raydan[9]將BB步長與GLL非單調(diào)線搜索技術(shù)[10]相結(jié)合,提出了GBB算法,證明了該方法是全局收斂的,求解一般無約束優(yōu)化問題的BB類方法也得到了發(fā)展,如文獻(xiàn)[11-13]等。

本研究考慮一般無約束優(yōu)化問題(1),對(duì)文獻(xiàn)[8]提出的兩種修正的BB步長采用凸組合形式,對(duì)凸組合參數(shù)利用循環(huán)使用步長的策略推導(dǎo)一個(gè)新步長,通過自適應(yīng)截?cái)嗖呗栽O(shè)計(jì)了一種高效的BB梯度法,驗(yàn)證了該算法的有效性。

1 新步長推導(dǎo)

針對(duì)問題(1),2017年,Zheng[8]提出修正割線方程的兩種BB類步長：

(4)

Dai等[15]考慮用Broyden族公式：

(5)

校正割線方程Hkyk-1=sk-1中的Hk,則有：

(6)

其中,Hk=[?2f(xk)]-1,τ∈[0,1],用D=αI近似Hessian矩陣及其逆矩陣,求解問題：

(7)

(8)

可得：

(9)

從而有：

(10)

(11)

(12)

可得：

(13)

(14)

根據(jù)以上對(duì)凸組合參數(shù)μk的選取,可得一個(gè)新步長：

(15)

根據(jù)以上兩種情形,結(jié)合Zhang-Hager非單調(diào)線搜索[17]提出一類新的自適應(yīng)截?cái)郆B梯度法(ATMBB法),步長為：

(16)

2 ATMBB算法

算法1 (ATMBB算法)。

第三步：Zhang-Hager非單調(diào)線搜索,若：

(17)

成立,執(zhí)行第四步,否則,通過下式更新α,并執(zhí)行第三步。

(18)

第四步：Qk+1=ηkQk+1,Ck+1=(ηkQkCk+fk+1)/Qk+1,ηk∈[ηmin,ηmax]。

第五步：αk=α,xk+1=xk-αkgk,k=k+1,執(zhí)行第一步。

3 收斂性分析

為證明提出的ATMBB算法是全局收斂的且具有線性收斂速度,對(duì)目標(biāo)函數(shù)做如下假設(shè)：

假設(shè)A 1)f(x)在Rn上有下界;

2)梯度g(x)在Rn上Lipschitz連續(xù),即?L>0,使得：

fk≤Ck≤Ak。

引理2 若假設(shè)A成立,{αk}是ATMBB算法產(chǎn)生的步長序列,則?ξ>0,使得：

αk≥ξ

(19)

為驗(yàn)證ATMBB算法的全局收斂性并給出線性收斂結(jié)果,證明如下：

定理3 若假設(shè)A成立,設(shè){xk}是由ATMBB算法產(chǎn)生的迭代點(diǎn)列,則有：

(20)

若ηmax<1,則有：

(21)

證明：

又Ck+1=(ηkQkCk+fk+1)/Qk+1,有：

由引理1可知,fk≤Ck,即Ck有下界,故有：

定理4 若假設(shè)A成立且f：Rn→R為強(qiáng)凸函數(shù),x*是一般無約束優(yōu)化問題的唯一極小點(diǎn),ηmax<1,{xk}是由ATMBB算法產(chǎn)生的迭代點(diǎn)列,則?θ∈(0,1),使得：

f(xk)-f(x*)≤θk(f(x0)-f(x*)),?k≥0

4 數(shù)值試驗(yàn)

bmax=1030,bmin=10-30,ηk=1,ε=10-6,δ=10-4,

為了更直觀地比較4種方法的數(shù)值效果,繪制了迭代次數(shù)、函數(shù)值計(jì)算次數(shù)、梯度值計(jì)算次數(shù)及CPU計(jì)算時(shí)間(以秒為單位)的性能曲線,如圖1、圖2、圖3、圖4。從圖中可以看出,無論是在迭代次數(shù)和函數(shù)值計(jì)算次數(shù)上,還是在梯度值計(jì)算次數(shù)和CPU計(jì)算時(shí)間上,ATMBB方法都優(yōu)于其他三種方法。

圖1 迭代次數(shù)性能曲線Fig.1 Curve of the number of iterations performance

圖2 函數(shù)值計(jì)算次數(shù)性能曲線Fig.2 Curve of the function value calculation times performance

圖3 梯度計(jì)算次數(shù)性能曲線Fig.3 Curve of gradient calculation times performance

圖4 計(jì)算時(shí)間性能曲線Fig.4 Curve of calculation times performance

5 結(jié)束語