摘 要：將修正的割線方程和BB梯度法結(jié)合起來(lái)，從而得到一類修正的BB步長(zhǎng)，再利用Zhang-Hager非單調(diào)線搜索，提出一個(gè)改進(jìn)的BB梯度方法（MB法）。在一定的假設(shè)下，MB法是具有全局收斂性的。同時(shí)對(duì)MB法和同類型的幾個(gè)BB方法進(jìn)行大量的數(shù)值試驗(yàn)，結(jié)果表明MB法的數(shù)值效果是最好的。

關(guān)鍵詞：Barzilai-Borwein梯度法；非單調(diào)線搜索；無(wú)約束優(yōu)化；改進(jìn)割線方程

中圖分類號(hào)：O224? ?文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：1674-0033（2024）02-0022-04

引用格式：楊爽藝.基于修正割線方程的BB梯度法[J].商洛學(xué)院學(xué)報(bào)，2024，38（2）：22-25.

BB Gradient Method Based on Modified Secant Equation

YANG Shuang-yi

（College of Mathematical Sciences， Chongqing Normal University， Shapingba? 401331， Chongqing）

Abstract： A modified BB gradient method （MB method） is proposed by combining the modified secant equation with the BB gradient method， thus obtaining a class of modified BB steps， and then using Zhang-Hager nonmonotonic line search. Under certain assumptions， the MB method is globally convergent. A large number of numerical experiments are also conducted on the MB method and several BB methods of the same type， and the results show that the MB method is the best numerically.

Key words： Barzilai-Borwein gradient method; nonmonotone line search; unconstrained optimization; modified secant equation

對(duì)于求解無(wú)約束優(yōu)化問(wèn)題：

f（x）? ? （1）

其中，f（x）：Rn→R為連續(xù)可微函數(shù)，n是變量的個(gè)數(shù)，x為決策變量。梯度法是解決這類問(wèn)題最簡(jiǎn)單的方法之一，其迭代格式為：

xk+1=xk-αkgk? ? （2）

其中，gk是f在xk處的梯度，αk是步長(zhǎng)，不同的步長(zhǎng)對(duì)應(yīng)著不同的梯度法。

文獻(xiàn)[1]在最小二乘意義下去近似標(biāo)準(zhǔn)割線方程Bksk-1=yk-1和Hkyk-1=sk-1中的Bk和Hk，得到步長(zhǎng)的兩個(gè)表達(dá)式：

[αBB1][k]=

（3）

[αBB2][k]=

其中，sk-1=xk-xk-1，yk-1=gk-gk-1。

[αBB1][k]和[αBB2][k]被稱為兩點(diǎn)步長(zhǎng)或者BB步長(zhǎng)，對(duì)應(yīng)的梯度法被稱為BB梯度法，簡(jiǎn)稱BB法。BB法擁有更快的收斂速度，同時(shí)還避免了一些復(fù)雜的計(jì)算。BB法的良好性能激起了研究者對(duì)BB法的研究。文獻(xiàn)[2]估計(jì)迭代點(diǎn)的單純形梯度，對(duì)BB法進(jìn)行改進(jìn)。文獻(xiàn)[3]利用循環(huán)策略去更新BB步長(zhǎng)。盡管許多研究者提出了一些改進(jìn)的BB法，但對(duì)最優(yōu)的BB梯度法還未達(dá)成共識(shí)。文獻(xiàn)[4]基于文獻(xiàn)[5]提出的割線方程，推導(dǎo)出了6個(gè)修正的BB步長(zhǎng)。文獻(xiàn)[6]基于文獻(xiàn)[7]提出的修正割線方程，并提出了改進(jìn)BB步長(zhǎng)。這些方法都表明，從割線方程角度去修正的BB法是可行的，但是數(shù)值性能上還存在一定缺陷?；诖?，本文在文獻(xiàn)[8]的研究基礎(chǔ)上，進(jìn)一步優(yōu)化，結(jié)合一個(gè)具有更好性質(zhì)的割線方程來(lái)修正BB法。

1? 修正的BB梯度法（MB）的算法

在文獻(xiàn)[9]中，令f（x）的Hessian矩陣Q（xk）取近似Bk和Bk+1，從而提出一個(gè)改進(jìn)的割線方程：

Bksk-1=wk-1=2yk-1+uk-1? ? ? ?（4）

其中，uk-1=gk。

將這個(gè)割線方程和BB法結(jié)合起來(lái)，用wk-1代替原BB1步長(zhǎng)中的yk-1，則得到一個(gè)新的步長(zhǎng)：

[αMB][k]=? ? ? ? （5）

其中，sk-1=xk-xk-1，yk-1=gk-gk-1。

基于文獻(xiàn)[10]中的算法框架，提出了一個(gè)修正的BB型算法（MB法）。

選擇初始步長(zhǎng)后，利用Zhang-Hager非單調(diào)線搜索[11]來(lái)計(jì)算后面的近似步長(zhǎng)。

步驟1? 給定初始值x0∈Rn，λmax≥λmin≥0，ε，γ∈（0，1），ηk∈[0，1]，0<σ1<σ2<1；計(jì)算f0，令C0=f0，Q0=1，α0=1，k=0。

步驟2? 若‖gk‖∞≤ε，停止迭代；否則，令dk=-αkgk。

步驟3? 計(jì)算步長(zhǎng)αk（非單調(diào)線搜索）。

先令t=1，若滿足：

f（xk+αkdk）≤Ck+γtαkg[k][T]dk? ? ? ?（6）

再令xk+1=xk+tαkdk，轉(zhuǎn)向步驟4。否則，選擇t∈[σ1t，σ2t]，轉(zhuǎn)向步驟2。

步驟4? 用式（5）和式（6）計(jì)算步長(zhǎng)，若αk<0，則令αk=λmax。否則，令αk=min{λmax，max{λmin，αk}}，轉(zhuǎn)向步驟5。

步驟5? 選擇ηk∈[ηmin，ηmax]，并計(jì)算：

Qk+1=ηkQk+1，Ck+1=。

步驟6? 令k=k+1，轉(zhuǎn)向步驟2。

2? 收斂性分析

假設(shè)1? 水平集Ω={x∈R：f（x）≤f（x0）}有界，即存在一個(gè)常數(shù)M>0，有：

‖x‖≤M，?x∈Ω ? ? ? ?（7）

假設(shè)2? 目標(biāo)函數(shù)f在Ω的某個(gè)鄰域N連續(xù)可微，且梯度▽f Lipschitz連續(xù)，即存在常數(shù)L>0，有：

‖g（x）-g（x*）‖≤L‖x-x*‖， ?x，x*∈N? ? ? ? （8）

引理1? 設(shè)Ak是關(guān)于k的平均函數(shù)值，即Ak=fi。如果對(duì)于任意k都滿足▽f（xk）dk≤0，那么在第k次迭代過(guò)程中，對(duì)任意的ηk，都有fk≤Ck≤Ak。

證明：令Dk（t）= ? ? ? ? ? ? （9）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?其中，D：R→R。

求導(dǎo)可得：

D[′][k]（t）= ? ? ? ? ? ? ? ? ? ? ? ?（10）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?由于fk≤Ck-1，所以對(duì)任意的t≥0，都有D[′][k]（t）≥0，即Dk（t）是單調(diào)遞增的。

故有：

fk=Dk（0）≤Ck ? ? ? ? ? ? ? ? ? ? ?（11）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 即Ck有下界，然后用歸納法證明Ck有上界。

當(dāng)k=0時(shí)，有C0=f（x0）成立。

現(xiàn)假設(shè)對(duì)任意的0≤j

Qj+1=1+ηj-m≤j+2 ? ? ? ? ? ? ? （12）? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 又由于Dk（t）是單調(diào)遞增的，則有：

Ck=Dk（Qk-1）≤Dk（k）=≤=Ak （13）

結(jié)合式（11）和式（13）可得fk≤Ck≤Ak，故得證。

進(jìn)一步，在[αmin，αmax]中選擇步長(zhǎng)αk，則存在兩個(gè)常數(shù)c1和c2，使得搜索方向dk滿足：

g[k][T]dk≤-c1‖gk‖2，‖dk‖≤c2‖gk‖，?k∈R （14）

定理1? 在假設(shè)1和假設(shè)2條件下，設(shè)MB法產(chǎn)生的迭代點(diǎn)列為{xk}，那么就存在某個(gè)有限的k，使得‖gk‖=0，或者‖gk ‖=0。進(jìn)一步，當(dāng)ηmax<1時(shí)，有‖gk‖=0。因此，迭代的每個(gè)收斂子序列都會(huì)接近一個(gè)點(diǎn)x*，其中▽f（x*）=0。

證明：令

β=min

，

，

（15）

當(dāng)ραk≥μ時(shí)，結(jié)合式（6）可得：

fk+1≤Ck+γαkg[k][T]dk≤Ck-‖gk ‖2（16）

則fk+1≤Ck-β‖gk ‖2成立。

當(dāng)ραk≤μ時(shí)有：

fk+1≤Ck-

（17）

結(jié)合式（14）有：

fk+1≤Ck-

‖gk ‖（18）

則fk+1≤Ck-β‖gk ‖成立。

綜上可得：

Ck+1=≤Ck-? ?（19）

又由引理1可知，對(duì)任意的k都有fk≤Ck，因此有<∞，即存在某個(gè)有限的k，使得‖gk‖=0，或者‖gk‖=0；當(dāng)ηmax<1時(shí)，‖gk‖=0

也成立，故得證。

3? 數(shù)值試驗(yàn)

Zhang-Hager線搜索過(guò)程中的參數(shù)分別為γ=10-4，ηk=0.7，σ=0.8，另外兩個(gè)參數(shù)分別為λmax=1030，λmin=10-30，終止準(zhǔn)則為：

‖gk ‖∞≤10-6（20）

當(dāng)?shù)螖?shù)超過(guò)5 000時(shí)也會(huì)終止。本文從文獻(xiàn)[12]中選擇了80個(gè)測(cè)試函數(shù)，它們的維數(shù)介于100～100 000，算法的測(cè)試環(huán)境為聯(lián)想Windows10操作系統(tǒng)，Intel（R） Core（AMD） R5-5600H CPU@ 2.10Ghz2.10Ghz，16GB內(nèi)存。

本文采用Dolan等[13]設(shè)計(jì)的性能圖來(lái)評(píng)估不同步長(zhǎng)對(duì)應(yīng)的梯度法的數(shù)值性能，采用這種評(píng)估方法的原因是這種方法可以更加直觀地觀察出這幾種方法的數(shù)值性能情況。為了方便，本文將α、文獻(xiàn)[14-15]中提出的試驗(yàn)效果較好的步長(zhǎng)和，所對(duì)應(yīng)的梯度法稱為M1、M2、M3。將M1、M2、M3和MB法做數(shù)值比較。這四種方法的性能曲線圖，如圖1所示。

數(shù)值試驗(yàn)通過(guò)求解大量問(wèn)題，將四種梯度法從計(jì)算時(shí)間、迭代次數(shù)、梯度計(jì)算次數(shù)和函數(shù)計(jì)算次數(shù)四個(gè)維度進(jìn)行比較。圖1（a）是對(duì)四種梯度法的計(jì)算時(shí)間的比較，發(fā)現(xiàn)MB法解決問(wèn)題花費(fèi)的計(jì)算時(shí)間最少。圖1（b）是對(duì)四種梯度法的迭代次數(shù)的比較，發(fā)現(xiàn)MB法迭代次數(shù)最少。圖1（c）是對(duì)四種梯度法的梯度計(jì)算次數(shù)的比較，發(fā)現(xiàn)MB法的梯度計(jì)算次數(shù)最少。圖1（d）對(duì)四種梯度法的函數(shù)計(jì)算次數(shù)的比較，發(fā)現(xiàn)MB法的函數(shù)計(jì)算次數(shù)最少。

從圖1可見(jiàn)，在計(jì)算時(shí)間、迭代次數(shù)、梯度計(jì)算次數(shù)和函數(shù)計(jì)算次數(shù)上看，MB法始終表現(xiàn)得最好，這就說(shuō)明，MB法具有比較好的數(shù)值效果。

4? 結(jié)語(yǔ)

將改進(jìn)割線方程和BB梯度法結(jié)合起來(lái)，得到一個(gè)新的步長(zhǎng)——MB步長(zhǎng)，再結(jié)合非單調(diào)線搜索得到MB法。通常的步長(zhǎng)只使用了當(dāng)前迭代點(diǎn)和上一迭代點(diǎn)的值及梯度值，但是MB步長(zhǎng)還使用了當(dāng)前迭代點(diǎn)和上一迭代點(diǎn)的函數(shù)值，因此充分利用了迭代點(diǎn)的信息。通過(guò)收斂性分析得到MB法是全局收斂的，并且不需要對(duì)目標(biāo)函數(shù)作任何的凸性假設(shè)。數(shù)值試驗(yàn)結(jié)果表明，從時(shí)間、迭代次數(shù)、函數(shù)計(jì)算次數(shù)和梯度計(jì)算次數(shù)上來(lái)看，MB法都具有較好的計(jì)算效率。

參考文獻(xiàn)：

[1]? JONATHAN B， BORWEIN J M. Two point step-size methods[J].Ima Journal on Numerical Analysis，1988（1）：1.

[2]? 鄭鵬遠(yuǎn)，李琴，孫忠林.基于Barzilai-Borwein梯度法的多微電網(wǎng)系統(tǒng)遞階優(yōu)化調(diào)度算法[J].科學(xué)技術(shù)與工程，2020，20（30）：12443-12451.

[3]? 楊奕涵.帶有循環(huán)策略的自適應(yīng)截?cái)郆B梯度法研究[J].黑龍江科學(xué)，2023，14（20）：54-57.

[4]? BABAIE-KAFAK S， FATEMI M. A modified two-point stepsize gradient algorithm for unconstrained minimization[J].Optimization Methods and Software，2013，28（5）：1040-1050.

[5]? LI D H， FUKUSHIMA M. A modified BFGS method and its global convergence in nonconvex minimization[J].Journal of Computational and Applied Mathematics，2001，129（1-2）：15-35.

[6]? 鄭燏濤.Barzilai-Borwein梯度法及其在優(yōu)化算法中的應(yīng)用[D].蘭州：蘭州大學(xué)，2018：11-24.

[7]? FORD J A， MOGHRABI I A. Multi-step quasi-Newton methods for optimization[J].Journal of Computational and Mathematics，1994，50（93）：305-323.

[8]? 陳旦.基于混合割線方程修正的BB梯度法[J].綿陽(yáng)師范學(xué)院學(xué)報(bào)，2023，42（2）：8-14.

[9]? HASSAN B A， MOGHRABI I A R. A modified secant equation quasi-Newton method for unconstrained optimization[J].Journal of Applied Mathematics and Computing，2023，69：451-464.

[10] BIGLARI F， SOLIMANPUR M. Scaling on the spectral gradient method[J].Journal of Optimization Theory and Applications，2013，158（2）：626-635.

[11] HAGER W W， ZHANG H. A new conjugate gradient method with guaranteed descent and an efficient line search[J].SIAM Journal on Optimization，2005，16（1）：170-192.

[12] GOULD N I M， ORBAN D， TOINT P L. CUTEr and SifDec： a constained and unconstrained testing environment， revisited[J].Acm Trainscations on

Mathematical Software，2003，29（4）：373-394.

[13] DOLAN E， MOR? J J. Benchmarking optimization software with performance profiles[J].Mathematical Programming，2001，91：201-213.

[14] XIAO Y， WANG Q， WANG D. Notes on the Dai-Yuan-Yuan modified spectral gradient method[J].Journal of Computational and Applied Mathematics，2010，234（10）：2986-2992.

[15] ZHANG J Z， DENG N Y， CHEN L H. New quasi-newton equation and related methods for unconstrained optimization[J].Journal of Optimization Theory and Applications，1999，102（1）：147-167.