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

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

中圖分類號：O224? ?文獻標識碼：A文章編號：1674-0033（2024）02-0022-04

引用格式：楊爽藝.基于修正割線方程的BB梯度法[J].商洛學(xué)院學(xué)報，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

對于求解無約束優(yōu)化問題：

f（x）? ? （1）

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

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

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

文獻[1]在最小二乘意義下去近似標準割線方程Bksk-1=yk-1和Hkyk-1=sk-1中的Bk和Hk，得到步長的兩個表達式：

[αBB1][k]=

（3）

[αBB2][k]=

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

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

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

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

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

其中，uk-1=gk。

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

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

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

基于文獻[10]中的算法框架，提出了一個修正的BB型算法（MB法）。

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

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

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

步驟3? 計算步長α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）計算步長，若αk<0，則令αk=λmax。否則，令αk=min{λmax，max{λmin，αk}}，轉(zhuǎn)向步驟5。

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

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

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

2? 收斂性分析

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

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

假設(shè)2? 目標函數(shù)f在Ω的某個鄰域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。如果對于任意k都滿足▽f（xk）dk≤0，那么在第k次迭代過程中，對任意的ηk，都有fk≤Ck≤Ak。

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

求導(dǎo)可得：

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

故有：

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

當k=0時，有C0=f（x0）成立。

現(xiàn)假設(shè)對任意的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，故得證。

進一步，在[αmin，αmax]中選擇步長αk，則存在兩個常數(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)生的迭代點列為{xk}，那么就存在某個有限的k，使得‖gk‖=0，或者‖gk ‖=0。進一步，當ηmax<1時，有‖gk‖=0。因此，迭代的每個收斂子序列都會接近一個點x*，其中▽f（x*）=0。

證明：令

β=min

，

，

（15）

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

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

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

當ραk≤μ時有：

fk+1≤Ck-

（17）

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

fk+1≤Ck-

‖gk ‖（18）

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

綜上可得：

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

又由引理1可知，對任意的k都有fk≤Ck，因此有<∞，即存在某個有限的k，使得‖gk‖=0，或者‖gk‖=0；當ηmax<1時，‖gk‖=0

也成立，故得證。

3? 數(shù)值試驗

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

‖gk ‖∞≤10-6（20）

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

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

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

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

4? 結(jié)語

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

參考文獻：

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

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

[3]? 楊奕涵.帶有循環(huán)策略的自適應(yīng)截斷BB梯度法研究[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].綿陽師范學(xué)院學(xué)報，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.