帶有延遲步長的循環(huán)BB梯度法

楊奕涵

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

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

(1)

其中目標(biāo)函數(shù)f:Rn→R是連續(xù)可微的。求解問題(1)的方法主要有線搜索方法和信賴域方法, 而梯度法是線搜索方法中的一類簡單迭代方法, 它以負(fù)梯度方向作為搜索方向, 其迭代格式為

xk+1=xk-αkgk,

(2)

其中g(shù)k?g(xk)=?f(xk),αk為步長。由于搜索方向已定, 梯度法求解無約束優(yōu)化問題便轉(zhuǎn)化為研究步長αk的選取, 不同的步長選取會導(dǎo)致梯度法具有不同的性能。因此, 如何設(shè)計一個有效的步長, 使得問題(1)能被快速求解, 且收斂性具有一定的理論保證, 是研究梯度法的重要問題之一。

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

(3)

其中sk-1=xk-xk-1,yk-1=gk-gk-1, 得到兩個兩點步長公式為

兩點步長又稱為BB步長, 相應(yīng)的梯度法稱為BB梯度法, 簡稱BB法。對于f為嚴(yán)格凸二次函數(shù)的情形, Barzilai和Borwein證明了當(dāng)n=2時, BB法具有R-超線性收斂速度。自BB法的提出, 極大地改善了梯度法的效率, 其理論上的結(jié)果有: 1993年Raydan[3]證明了當(dāng)f為任意維嚴(yán)格凸二次函數(shù)時, BB法是全局收斂的, 并且2002年Dai和Liao[4]進一步證明了BB法具有R-線性收斂速度。此外, 也吸引了眾多學(xué)者對該方法做一系列研究, 從不同的角度推導(dǎo)了不同類型的BB步長, 如文獻[6]-[15]等。

如果直接將BB法推廣至求解一般無約束優(yōu)化問題, 即使目標(biāo)函數(shù)是嚴(yán)格凸函數(shù), 該方法也可能不收斂。因此為保證其收斂性, Raydan[5]在1997年首次將BB步長與GLL非單調(diào)線搜索技術(shù)[16]相結(jié)合, 并證明了該方法是全局收斂的。隨后, 求解一般無約束優(yōu)化問題的BB類方法得到發(fā)展, 如文獻[17]-[19]等。

本文考慮一般無約束優(yōu)化問題(1), 基于延遲(retard)策略, 采用前一步迭代的步長為當(dāng)前迭代步長提供一些重要信息, 推導(dǎo)出一個求解一般無約束優(yōu)化問題的步長, 進而設(shè)計一類高效的BB梯度法。本文的結(jié)構(gòu)安排如下:1)給出了求解一般無約束優(yōu)化問題的新梯度法, 并進行了討論;2)給出了本文提出的算法框架;3)給出了該算法的全局收斂性和線性收斂率;4)數(shù)值試驗驗證了與現(xiàn)有技術(shù)相比, 所提出的梯度算法在計算上更高效。

1 新步長的推導(dǎo)

對于嚴(yán)格凸二次極小化問題:

(4)

其中A∈Rn×n對稱正定,b∈Rn。 2022年Huang等人[15]提出了步長:

(5)

A,可得一個求解二次問題的步長:

αk=

(6)

2022年, Zhang和Sun[19]將二次極小化問題推廣到求解一般光滑無約束優(yōu)化問題, 考慮構(gòu)造前一步BB步長來近似當(dāng)前Cauchy步長, 其迭代格式為

(7)

(8)

(9)

(10)

由于近年來出現(xiàn)了循環(huán)步長更新策略, 如SDC方法[21], 它需要h(≥2)步Cauchy步長(3), 及通過(9)式計算m個固定步長, 其更新策略為

(11)

(12)

進而Zhang和Sun在文獻[19]中提出了一種新的循環(huán)梯度法, 其步長為:

(13)

(14)

(15)

考慮二次函數(shù)的極小化問題[23]:

(16)

下一節(jié), 我們將給出步長(16)與Zhang-Hager非單調(diào)線搜索技術(shù)[24]相結(jié)合而設(shè)計的循環(huán)BB梯度算法(CBBGM算法)。

2 CBBGM算法

第一步若‖gk‖∞≤ε, 停止。

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

f(xk-αgk)≤Ck-δα‖gk‖2,

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

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

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

3 收斂性分析

本節(jié)將證明提出的CBBGM算法是全局收斂的, 并且具有線性收斂速度。下面先對目標(biāo)函數(shù)做如下假設(shè)。

假設(shè)A 1)f(x)在Rn中連續(xù)可微;

2)f(x)在Rn上有下界;

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

‖g(x)-g(y)‖≤L‖x-y‖, ?x,y∈Rn。

由文獻[24]中的引理1.1可以直接得到下面的引理1。

fk≤Ck≤Ak.

為分析CBBGM算法的全局收斂性和線性收斂率, 現(xiàn)需證明下面定理1。

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

αk≥ξ,

(19)

f(xk-ραkgk)>Ck-δραk‖gk‖2≥fk-δραk‖gk‖2.

(20)

因為?f(xk)是 Lipschitz連續(xù)的, 所以

f(xk-αkgk)-f(xk)=

(21)

參照文獻[24]中的定理2.2和定理3.1的證明方法, 可以得到CBBGM算法的全局收斂性和線性收斂結(jié)果。

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

(22)

此外, 若ηmax<1, 則有

(23)

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

(24)

4 數(shù)值試驗

為了更直觀的比較四種方法的數(shù)值效果, 本文繪制了迭代次數(shù)、函數(shù)值計算次數(shù)、梯度值計算次數(shù)和CPU計算時間的性能曲線圖, 如圖1～圖4。從圖中可以看出, 在迭代次數(shù)、函數(shù)值計算次數(shù)、計算時間上, 本文提出的CBBGM方法與其他方法相比, 都具有競爭力。在梯度值計算次數(shù)上, 由于CBBGM方法是基于上一步的步長信息, 于是在計算下一個步長時, 會計算兩次梯度值, 但是CBBGM方法與其他三種方法也是可比的。

圖1 迭代次數(shù)性能曲線

圖2 函數(shù)值計算次數(shù)性能曲線

圖3 梯度值計算次數(shù)性能曲線

圖4 計算時間性能曲線

5 結(jié)語