楊奕涵

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

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

(1)

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

xk+1=xk-αkgk,

(2)

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

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

(3)

其中sk-1=xk-xk-1,yk-1=gk-gk-1, 得到兩個(gè)兩點(diǎn)步長(zhǎng)公式為

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

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

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

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

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

(4)

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

(5)

A,可得一個(gè)求解二次問(wèn)題的步長(zhǎng):

αk=

(6)

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

(7)

(8)

(9)

(10)

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

(11)

(12)

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

(13)

(14)

(15)

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

(16)

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

2 CBBGM算法

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

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

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

成立, 執(zhí)行第四步; 否則, 通過(guò)下式更新α, 并執(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算法是全局收斂的, 并且具有線性收斂速度。下面先對(duì)目標(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。

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

fk≤Ck≤Ak.

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

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

αk≥ξ,

(19)

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

(20)

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

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

(21)

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

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

(22)

此外, 若ηmax<1, 則有

(23)

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

(24)

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

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

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

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

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

圖4 計(jì)算時(shí)間性能曲線

5 結(jié)語(yǔ)