無約束優(yōu)化的非單調(diào)三次正則BB算法

楚王莉,劉紅衛(wèi),劉澤顯

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

0 引 言

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

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

(1)

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

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

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

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

1 算法設(shè)計

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

(2)

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

其中

(3)

對子問題用求導(dǎo)的方式求極值,可得

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的正定性.為了得到當(dāng)前點處的試探步sk,需要構(gòu)造新的三次近似模型以簡化三次正則算法子問題的求解.考慮三次正則子問題：

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

(8)

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

則式(8)可表示為

(9)

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

(10)

(11)

因此由式(11)易得

從而可得一個新的三次近似最優(yōu)模型：

(12)

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

(13)

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

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

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

由構(gòu)造的三次近似模型對目標函數(shù)的預(yù)測下降量為

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

則

(14)

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

(15)

式中

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

如果Ared(sk)和Pred(sk)的比值ρk在一定范圍內(nèi),則可保持正則參數(shù)不變或者減少,此時可接受試探步sk,則有xk+1=xk+sk,否則,增加正則化參數(shù)σk,并在當(dāng)前迭代點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,更新正則參數(shù)：

(16)

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

(17)

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

考慮到BB類型算法的非單調(diào)性,本文將一些非單調(diào)策略應(yīng)用到三次正則BB算法的框架中.在本文算法中,當(dāng)試探步產(chǎn)生的函數(shù)值實際下降量不能與預(yù)測值下降量有一定的匹配度時,試探步被拒絕.考慮到當(dāng)?shù)h離最優(yōu)點時,使用非單調(diào)策略能獲得更佳的收斂結(jié)果,因此采用非單調(diào)線搜索策略以避免子問題的重復(fù)求解.

下面結(jié)合非單調(diào)線搜索策略,給出非單調(diào)三次正則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)更新正則參數(shù), 轉(zhuǎn)步驟5).

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

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

2 收斂性分析

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

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

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

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

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

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

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

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

引理2假設(shè)試探步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)不會無限循環(huán).

證明：對于步驟4),當(dāng)ρk

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

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

若αk→0,則有

(18)

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

(19)

證明：當(dāng)ρk

當(dāng)ρk≥v時,用反證法.假設(shè)存在一個常數(shù)τ>0,使得對任意的k,有

‖gk‖≥τ,

(20)

則有

結(jié)合Ck的定義,可得

再結(jié)合假設(shè)式(20)可知

(21)

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

(22)

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

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

(23)

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

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

3 數(shù)值實驗

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

本文所有算法程序均由C語言實現(xiàn),每個測試問題的維數(shù)都為104,算法中用到的參數(shù)為：ε=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.當(dāng)滿足‖gk‖∞≤10-6時,算法停止迭代,迭代次數(shù)超過5×104或者函數(shù)的計算次數(shù)超過8×104時,算法也停止迭代.

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

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

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

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

圖3 兩種算法梯度計算次數(shù)的性能評估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種算法迭代次數(shù)的性能評估Fig.5 Performance evaluation of iteration numbers for three algorithms

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

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

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

圖7 3種算法函數(shù)值計算次數(shù)的性能評估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

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

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