無約束優化的非單調三次正則BB算法

楚王莉,劉紅衛,劉澤顯

(1.西安電子科技大學 數學與統計學院,西安 710126；2.中國科學院 數學與系統科學研究院,北京 100190)

0 引 言

目前,求解無約束優化問題的方法主要分為兩類: 線搜索法和信賴域法.線搜索法主要有牛頓法、擬牛頓法、梯度法、共軛梯度法,其中梯度算法以其計算簡單、易于存儲的特點更適應現代大數據計算的要求.

考慮一般無約束優化問題：

(1)

其中:f:n→是目標函數;x是決策變量.最簡單的梯度算法是最速下降法[1],其步長也被稱為Cauchy步長或者最優步長、精確步長,算法在迭代點接近極小點時,易產生鋸齒現象.Barzilai-Borwein算法(簡稱BB算法)[2]以其良好的數值性能得到廣泛關注,目前已成為求解大規模優化問題的重要方法之一.BB算法中的兩個BB步長分別為

其中:sk-1=xk-xk-1;yk-1=gk-gk-1.本文中fk=f(xk),gk=g(xk),g(xk)=f(xk),‖·‖表示Euclid范數.對于嚴格凸二次函數,BB算法具有全局收斂性和R-線性收斂性[3-4],其計算效果遠超過最速下降法.但對于一般的目標函數,BB步長可能為負,不能保證目標值單調下降.Raydan[5]通過結合Grippo等[6]提出的非單調線搜索,設計了一種高效的用于求解無約束優化問題的全局BB算法.對于大多數問題,非單調BB算法的表現均較好.之后,許多學者從不同的角度推導出了不同類型的修正BB步長[7-8],數值實驗表明,修正的BB類型步長數值效果較好,但對于最優的BB步長目前尚未達成共識.Liu等[9]從近似模型的角度解釋了BB步長,引入了一類新的步長----近似最優步長,提出了一種高效的求解大規模無約束優化問題的近似最優梯度法.文獻[10-11]在文獻[9]的基礎上給出了幾種高效的求解一般無約束優化問題的近似最優梯度算法.

三次正則化算法是通過對目標函數取三次過高估計,在目標函數的二次估計上加上一個三次正則項,構成三次模型,作為一種正則化技術計算下一步迭代的步長,因此,三次正則模型比二次模型包含了更多的函數信息.近年來,三次正則化算法作為一種新的求解無約束優化問題的方法已被廣泛關注：Cartis等提出了一個自適應的三次正則算法(ARC)[12],并指出在較差條件下,ARC算法享有O(ε-3/2)的迭代復雜度[13].實際上,三次正則算法需要在子空間上進行多次迭代求解試探步,使子問題的求解變得更復雜,而且需要大量的計算和存儲空間,因此,構造出更接近目標函數的近似模型和高效求解三次正則化算法的子問題是三次正則化算法的核心.文獻[14]給出了一種計算立方模型近似最小值的方法；文獻[15]使用BB類型參數構造了一個非單調簡單模型的信賴域算法;基于非單調信賴域方法[16],文獻[17]給出了一種非單調三次過高估計算法；文獻[18]給出了一種將三次正則化方法與線搜索和非單調技術相結合的新算法.

本文首先利用修正的BB類型參數γk構造對角陣來近似目標函數的Hessian矩陣；然后利用近似最優步長構造當前迭代點處的三次正則化近似模型,通過極小化三次近似模型求解試探步,以降低試探步的計算成本,并給出三次正則BB算法；最后基于BB類型算法的非單調性質,為了在試探步長被拒絕時充分發揮BB類型步長的優勢,引入非單調策略,得到非單調三次正則BB算法.此外,還對本文算法的接受條件做了一些修正.在合理的假設條件下,給出本文算法的收斂性分析.數值實驗表明了本文算法具有良好的數值性能.

1 算法設計

考慮無約束優化問題(1),在當前迭代點,自適應三次正則化模型為

(2)

其中:Bk為目標函數f(x)的Hessian矩陣在xk處的近似;σk為正則化參數.問題(2)的解sk稱為當前迭代點處的試探步.設計算目標函數從xk到xk+sk的實際下降量與模型預測下降量之間的比率為ρk,若ρk>v,v∈(0,1),則試探步sk被接受,否則增加正則化參數σk,重新計算試探步.

其中

(3)

對子問題用求導的方式求極值,可得

gk+γks*+σk‖s*‖s*=0,

(4)

其中s*是式(3)的極小值,式(4)也可以寫為

gk+γks*+λ*s*=0,

(5)

其中λ*=σk‖s*‖,則由式(5)可得

s*=-[(γk+λ*)I]-1gk,

從而

(6)

由λ*≥0,對式(6)求解,易得

綜合上述計算,可解得式(3)的極小值為

sk=s*=-αkgk.

(7)

從而在試探步的計算過程中只需考慮一階信息,不需要Hessian矩陣存儲,使算法計算更簡便、存儲量小、效率高.

此時,情形1)中的BFGS更新不能保證Bk的正定性.為了得到當前點處的試探步sk,需要構造新的三次近似模型以簡化三次正則算法子問題的求解.考慮三次正則子問題：

試探步sk可表示為sk=αkdk,其中:αk為步長;dk為搜索方向,本文取dk=-gk.則試探步可近似實現Cauchy點的迭代效果.試探步可由下列計算得出：

(8)

對于足夠小的τk>0,有

則式(8)可表示為

(9)

由于τk>0,σk>0,式(9)的分母是正數,αk是近似最優步長,因此當前迭代點處試探步可表示為

(10)

(11)

因此由式(11)易得

從而可得一個新的三次近似最優模型：

(12)

參照式(8)的求解方式,可得新的試探步為

(13)

綜合上述兩種情形可得當前迭代點處的近似試探步,極大降低了三次正則算法子問題求解的計算難度.

考慮到三次正則算法試探步接受條件的計算,本文對比率ρk做一些改進,用Zhang-Hager線搜索方法[20]中的Ck代替當前點處的函數值,由上述計算過程可知sk是三次正則子問題的解,則目標函數值的實際下降量為

Ared(sk)=Ck-f(xk+sk),

由構造的三次近似模型對目標函數的預測下降量為

Pred(sk)=mk(0)-mk(sk),

則

(14)

其中Ck的取值參考Zhang-Hager線搜索[20]：

(15)

式中

參數ηk-1∈[ηmin,ηmax],ηmin∈[0,1),ηmax∈[ηmin,1].

如果Ared(sk)和Pred(sk)的比值ρk在一定范圍內,則可保持正則參數不變或者減少,此時可接受試探步sk,則有xk+1=xk+sk,否則,增加正則化參數σk,并在當前迭代點xk處重新求解子問題.

下面給出三次正則BB(簡稱ARC-BB)算法.

算法1ARC-BB算法.

初始點選取: 令x0為初始點,x0∈n,δ∈(0,1),常量ε>0,δ,ηmin,η1,ηmax,σ0,1≤γ1≤γ2,1≥v2≥v1>0,令Q0=1,C0=f0,k=0.

步驟1) 如果‖gk‖∞≤ε,則停止計算.

步驟3) 用式(14)計算比率ρk,如果ρk

步驟4) 令xk+1=xk+sk,更新正則參數：

(16)

步驟5) 選擇合適的ηk∈[ηmin,ηmax],按下式更新Qk+1和Ck+1：

(17)

令k=k+1,返回步驟1).

考慮到BB類型算法的非單調性,本文將一些非單調策略應用到三次正則BB算法的框架中.在本文算法中,當試探步產生的函數值實際下降量不能與預測值下降量有一定的匹配度時,試探步被拒絕.考慮到當迭代遠離最優點時,使用非單調策略能獲得更佳的收斂結果,因此采用非單調線搜索策略以避免子問題的重復求解.

下面結合非單調線搜索策略,給出非單調三次正則BB(簡稱NMARC-BB)算法.

算法2NMARC-BB算法.

初始點選取: 令x0為初始點,x0∈n,δ∈(0,1),常量ε>0,δ,ηmin,η1,ηmax,σ0,1≤γ1≤γ2,1≥u2≥u1>0,令Q0=1,C0=f0,k=0.

步驟1) 如果‖gk‖∞≤ε,則停止計算.

步驟3) 用式(14)計算比率ρk,如果ρkv,則令xk+1=xk+sk,按式(16)更新正則參數, 轉步驟5).

步驟4) 用文獻[15]更新

步驟5) 選擇合適的ηk∈[ηmin,ηmax],按式(17)更新Qk+1和Ck+1;令k=k+1,返回步驟1).

2 收斂性分析

下面給出ARC-BB和NMARC-BB算法的收斂性證明,主要由三次近似模型求得試探步sk的性質分析.

假設1 對模型mk(sk),對任意的k≥0,κB≥0,‖Bk‖≤κB均成立.

假設2f(x)在n上是連續可微的.

假設3 梯度g(x)在n上是Lipschitz連續的,即存在L>0,使得

‖g(x)-g(y)‖≤L‖x-y‖, ?x,y∈n.

由dk=-gk,易知搜索方向是下降方向.本文中試探步sk是通過極小化三次近似模型mk(sk)得到的,而mk(sk)實質上是一個梯度模型,因此試探步sk可表示為sk=-αkgk,其中αk可視為沿負梯度方向的步長.

引理1假設試探步sk是由ARC-BB和NMARC-BB算法計算得出的,則對任意的k≥0,有

證明：證明過程類似于文獻[12]中引理2.1,故略.

引理2假設試探步sk是由ARC-BB和NMARC-BB算法計算得出的,對任意的k≥0,有κB≥0,使得‖Bk‖≤κB成立,則

證明：證明過程類似于文獻[12]中引理2.2,故略.

引理3若序列{xk}是由ARC-BB和NMARC-BB算法計算得出的,則對任意的k≥0,有fk+1≤Ck+1≤Ck.

證明：證明過程類似于文獻[21]中引理3.1和文獻[20]中定理2.2,故略.

引理4NMARC-BB算法的步驟4)是合理的,即步驟4)不會無限循環.

證明：對于步驟4),當ρk

利用Taylor展式和引理3,可得

對于ξk∈(0,1),有

若αk→0,則有

(18)

定理1假設f有下界,序列{xk}是由ARC-BB和NMARC-BB算法計算得出的,則有

(19)

證明：當ρk

當ρk≥v時,用反證法.假設存在一個常數τ>0,使得對任意的k,有

‖gk‖≥τ,

(20)

則有

結合Ck的定義,可得

再結合假設式(20)可知

(21)

由引理3可知,對任意的k≥0,有fk+1≤Ck,且序列{Ck}是單調不增的,再結合假設f(x)在n上是連續可微的,則序列{Ck}是收斂的,因此

(22)

又由ηk∈[ηmin,ηmax]?[0,1]及Ck,Qk的定義可知

再結合式(21),(22)可得

(23)

因此,對任意的k∈Γ,第k次迭代都有

這與已知ρk≥v矛盾,從而式(19)成立.證畢.

3 數值實驗

下面先對所提出的兩種算法ARC-BB和NMARC-BB的數值性能進行比較,然后給出NMARC-BB算法與BB算法和GM-AOS(cone)[10]算法的數值實驗比較,其中BB算法是公認的解決無約束優化問題非常有效的方法,GM-AOS(cone)算法是目前數值效果非常好的近似最優梯度算法.本文使用與GM-AOS(cone)算法相同的測試函數集,即Andrei測試函數集中的80個測試函數(http://camo.ici.ro/neculai/AHYBRIDM).

本文所有算法程序均由C語言實現,每個測試問題的維數都為104,算法中用到的參數為：ε=10-6,v=0.01,v1=0.3,v2=0.7,γ1=1.5,γ2=2,ξ1=1.07,ξ2=0.85,σ0=50,δ=0.55,ηk=1,ηmax=ηmin=1,?=5.當滿足‖gk‖∞≤10-6時,算法停止迭代,迭代次數超過5×104或者函數的計算次數超過8×104時,算法也停止迭代.

本文利用Dolan等[22]提出的數值性能比較方法給出不同算法數值性能的比較結果.下面以迭代次數為例說明文獻[22]方法的性能圖.用函數P(τ)表示測試算法s在最少迭代次數集I*的τ倍內所能解的問題個數占總問題個數的比率,它反映了測試算法迭代次數的數值性能.對每種測試算法,給出P(τ)的曲線圖,最高的曲線表示該測試算法在最少迭代次數集的τ倍內能求解的問題最多,因此該測試算法在迭代次數方面的數值性能更好.

數值實驗分兩組,第一組先對ARC-BB和NMARC-BB算法進行比較,其中ARC-BB算法可以成功求解79個問題,NMARC-BB算法可以成功求解測試函數集中的全部80個問題.消除ARC-BB算法不可解的問題后,剩下79個問題,因此下面分析只考慮余下的79個問題.圖1～圖4分別為兩種算法的迭代次數、函數值計算次數、梯度計算次數以及CPU時間的性能評估結果.由圖1～圖4可見,NMARC-BB算法的數值效果好于ARC-BB算法.因此,在下面的數值實驗過程中,使用數值效果較好的NMARC-BB算法與其他算法比較.

圖1 兩種算法迭代次數的性能評估Fig.1 Performance evaluation of iteration numbers for two algorithms

圖2 兩種算法函數值計算次數的性能評估Fig.2 Performance evaluation of calculation numbers of function values for two algorithms

圖3 兩種算法梯度計算次數的性能評估Fig.3 Performance evaluation of calculation numbers of gradient for two algorithms

圖4 兩種算法的CPU性能評估Fig.4 Performance evaluation of CPU for two algorithms

圖5 3種算法迭代次數的性能評估Fig.5 Performance evaluation of iteration numbers for three algorithms

圖6 3種算法梯度計算次數的性能評估Fig.6 Performance evaluation of calculation numbers of gradient for three algorithms

第二組實驗對NMARC-BB、BB和GM-AOS(cone)3種算法的數值結果進行比較.結果表明,NMARC-BB算法可以成功解決80個測試函數集中的全部問題,GM-AOS(cone)算法可以成功求解79個問題,BB算法只能成功求解其中的74個問題.消除3種算法中不可解的問題后,剩下74個問題,因此下面分析中只考慮剩下的74個問題.圖5和圖6分別為NMARC-BB、BB和GM-AOS(cone)3種算法的迭代次數和梯度計算次數的比較結果.由圖5和圖6可見,NMARC-BB算法比BB和GM-AOS(cone)算法的數值性能更好,其中NMARC-BB算法迭代次數和梯度計算次數最小的問題占總問題的55%,BB算法和GM-AOS(cone)算法迭代次數和梯度計算次數最小的問題分別占總問題的44%和19%.

圖7為3種算法的函數計算次數性能評估結果.由圖7可見,NMARC-BB比BB算法具有更大的優勢,并且相對GM-AOS(cone)算法表現突出.NMARC-BB算法函數值計算次數最小的問題占總問題的62%,GM-AOS(cone)和BB算法函數值計算次數最小的問題分別占總問題的42%和21%.圖8為3種算法CPU運行時間的比較.由圖8可見,在解決本文所給的測試函數集函數時,NMARC-BB算法比BB和GM-AOS(cone)算法所用的時間更少.

圖7 3種算法函數值計算次數的性能評估Fig.7 Performance evaluation of calculation numbers of function values for three algorithms

圖8 3種算法CPU性能評估Fig.8 Performance evaluation of CPU for three algorithms

由上述實驗結果可見,NMARC-BB算法具有良好的數值性能,通過將三次正則技術與BB算法相結合給出的新的求解大規模無約束優化問題的NMARC-BB算法,比原有的BB類型算法更靈活、高效.

綜上所述,本文提出了兩種新的求解大規模無約束優化問題的ARC-BB和NMARC-BB算法.基于BB算法的高效性和簡潔性,利用一個BB類型參數近似目標函數的Hessian矩陣,通過構造當前迭代點處的三次近似梯度模型,用極小化三次近似模型的方法求解當前點處的試探步.在試探步被拒絕的情形下,利用非單調線搜索策略設計求解新的試探步.數值實驗結果表明,NMARC-BB算法不僅具有高效性和簡便性,同時還有比傳統的BB類型算法包含更多的函數值信息,更精確.