一種求解結(jié)構(gòu)組合優(yōu)化問題的BB型算法

李凱 林彭壯漢 胡子健 程萬友

(東莞理工學(xué)院 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院,廣東東莞 523808)

考慮以下無約束優(yōu)化問題:

(1)

(2)

(3)

近年來壓縮感知和稀疏優(yōu)化不斷發(fā)展,為了求解問題(3)式,人們提出了不同的求解方法,其中常見迭代閾值算法ISTA[4]算法,因其內(nèi)存需求低、迭代簡單的特點(diǎn),常用于求解大規(guī)模問題。為了加速ISTA[4]算法的收斂速度,Beck和Teboulle[5]提出了快速迭代收縮閾值算法(FISTA)。Wright[6]等人提出了可分離近似的稀疏重構(gòu)算法(SpaRSA),該方法使用帶保障的BB步長和非單調(diào)線搜索,算法的數(shù)值結(jié)果很好,適用于實(shí)際問題。此外求解問題(2)和(3)的算法還有乘子交替方向法SALSA[7]、內(nèi)點(diǎn)法[8]、梯度投影法[9]、近端梯度方法[2]等。

本文第1節(jié)將提出一種求解問題(3)的BB型算法,并分析算法的收斂性。在第2節(jié),通過數(shù)值實(shí)驗(yàn)與一些現(xiàn)有的算法進(jìn)行比較,證明了所提出算法的有效性。

1 算法描述

在本文中,使用Huang[10]等人提出新的BB步長來求解稀疏優(yōu)化問題。在一些假設(shè)下,證明了所提出算法的全局收斂性。算法的迭代格式如下:

xk+1=xk+βkdk,

其中dk是搜索方向,βk∈(0,1]是步長參數(shù)。由于目標(biāo)函數(shù)φ(x)是非光滑的,因此搜索方向不能使用負(fù)梯度方向,根據(jù)函數(shù)φ(x)的近似函數(shù)的極小值點(diǎn)來確定如下搜索方向:

dk=Pro(xk)-xk,

(4)

其中Pro(xk)是以下問題的極小值點(diǎn):

其中(αk)-1I是函數(shù)f(x)的Hessian矩陣?2f(xk)的近似,uk=xk-αk?f(xk)。顯然,函數(shù)Q(z,xk)可以看成是函數(shù)φ(x)在xk處的二次近似。由于函數(shù)Q(z,xk)是強(qiáng)凸函數(shù),因此問題(5)式有唯一最小值點(diǎn):

αk的選取會(huì)直接影響算法的效率,BB型算法以其快速收斂和較低的計(jì)算復(fù)雜度而受到廣泛關(guān)注,Barzilai和Borwein[11]提出了以下長和短的步長選擇:

其中sk-1=xk-xk-1,yk-1=?f(xk)-?f(xk-1)。在所提出的算法中使用了Huang[10]等人提出一種新的步長,其具體表達(dá)式如下:

其中

由于自適應(yīng)步長策略的成功應(yīng)用[12],使用自適應(yīng)步長

(6)

其中γ>1,這種可變設(shè)置使得步長策略在一些應(yīng)用中能夠得到顯著的性能改進(jìn)。為了避免步長太小或者太大,結(jié)合(6)式,使用帶保障的BB步長

(7)

其中0<αmin<αmax<∞,αmin,αmax為固定的參數(shù)。

Fletcher在文獻(xiàn)[13]中指出,BB方法的一個(gè)重要特征是其固有的非單調(diào)性,通常采用一些非單調(diào)線搜索來獲得好的數(shù)值性能。因此,采用文獻(xiàn)[14]中提出的非單調(diào)線搜索策略,若步長βk滿足不等式

(8)

則βk是可接受的步長,其中σ∈(0,1),Ck具有以下迭代形式:

(9)

參照文獻(xiàn)[14]中的設(shè)置,令C0=φ(x0),Q0=1,η∈(0,1)。下面給出求解問題(3)的非單調(diào)BB型算法。

算法1非單調(diào)BB型算法

2)若滿足算法的終止條件,則結(jié)束算法。否則,轉(zhuǎn)步驟3)。

3)根據(jù)(4)式計(jì)算搜索方向dk。

4)計(jì)算mk是使得βk=ρmk滿足不等式(8)的最小整數(shù),令xk+1=xk+βkdk。

5) 由(9)式計(jì)算Ck+1和Qk+1。

6) 由(7)式計(jì)算新的步長αk+1。

7) 令k:=k+1,轉(zhuǎn)步驟2)。

備注:對于步驟4的非單調(diào)線搜索,文獻(xiàn)[14]中指出Ck+1是Ck和φ(xk+1)的凸組合。因?yàn)镃0=φ(x0),因此可以得出Ck是函數(shù)φ(x0),φ(x1),…,φ(xk)的凸組合,對于所有的k,有φ(xk)≤Ck,η的選擇控制了非單調(diào)性的程度。

1.1 收斂性分析

設(shè)問題(3)式中的目標(biāo)函數(shù)滿足以下假設(shè):

假設(shè)1

2)在水平集S上,存在一個(gè)鄰域N,使得函數(shù)f(x)是連續(xù)可微的光滑函數(shù),且f(x)的梯度滿足Lipschitz連續(xù)性。也就是說,存在常數(shù)L>0,使得

0∈?φ(x*)=?f(x*)+?g(x*),

則x*是問題(3)的穩(wěn)定點(diǎn)。當(dāng)f(x)為凸函數(shù)時(shí),φ(x)也是凸函數(shù),則滿足條件的點(diǎn)x*是問題(3)的全局解。不難證明,對于任意給定的αk>0,若

為了證明算法的收斂性,首先介紹一些支撐主要證明的引理。參照文獻(xiàn)[6]中引理2和引理3的證明, 可以得到如下結(jié)果。

通過取極限i→∞,使用?g的閉性和αk的有界性,有0∈?f(x*)+?g(x*)=?φ(x*)成立。這與x*不是穩(wěn)定點(diǎn)相矛盾,因此證畢。

(10)

且dk是下降方向。若βk滿足不等式(10),則

(11)

(12)

由?f(x)的Lipschitz連續(xù)性和(12)式可知

φ(xk+βkdk)-φ(xk)=

(13)

因Pro(xk)=xk+dk是函數(shù)Q(z,xk)的唯一最小值,所以根據(jù)函數(shù)Q(z,xk)的定義(4)式有

Q(xk+dk,xk)=

(14)

由(14)式得

(15)

在非單調(diào)線搜索過程中,對于任意的k,有φ(xk)≤Ck,結(jié)合(13)和(15)式可得

φ(xk+βkdk)-Ck≤φ(xk+βkdk)-φ(xk)≤

(16)

所以當(dāng)

下面的定理表明當(dāng)目標(biāo)函數(shù)φ(x)是凸函數(shù)時(shí),算法1收斂到問題(3)的全局解。

定理1設(shè)假設(shè)1成立,φ(x)有下界,序列{xk}由算法1所產(chǎn)生,則其任意聚點(diǎn)都是問題(3)式的穩(wěn)定點(diǎn)。

證明因?yàn)?0<η<1,由(9)式和Q0=1可得

(17)

結(jié)合(9)、(10)和(17)式可得

(18)

因此{(lán)Ck}是非增的。因?yàn)棣?x)是有下界,所以{Ck}也是有下界的,所以對(18)式累加求和得

因?yàn)镃0-Ck+1是有限的,所以

(19)

2 數(shù)值實(shí)驗(yàn)

在本節(jié)中,通過數(shù)值實(shí)驗(yàn)來研究所提出算法的數(shù)值性能,并與一些現(xiàn)有算法進(jìn)行了比較。所有的數(shù)值實(shí)驗(yàn)都是由 MATLAB R2020a 編寫的,并搭載在windows10 系統(tǒng)的 PC 上運(yùn)行 (CPU:i5-7200U 2.50 GHz;內(nèi)存:8.00 GB)。

(20)

所有測試算法的初始點(diǎn)設(shè)置為x0=0，測試問題的終止條件為

(21)

表1 λ=1/m，=10-4的比較結(jié)果

表1 λ=1/m，=10-4的比較結(jié)果

數(shù)據(jù)集HZ_NBBHLBBASFISTAdatasetmniterfuntimeiterfuntimeiterfuntimeheart27013160.380 40.05170.380 40.09180.380 40.12colon-cancer622 000590.204 40.64730.203 31.02520.205 51.09diabetes7688160.623 50.24150.624 30.22590.619 41.86pyrim7427230.219 20.03300.218 30.05290.219 20.06splice1 00060210.379 50.44390.379 21.02850.379 62.32ionosphere35134300.371 40.18370.371 60.31350.371 60.39a2a2 265123260.358 41.66280.358 92.13750.358 64.44german.numer1 00024230.477 00.31250.477 80.41270.477 80.83

(續(xù)表)

表2 λ=1/m，=10-6的比較結(jié)果

表2 λ=1/m，=10-6的比較結(jié)果

數(shù)據(jù)集HZ_NBBHLBBASFISTAdatasetmnIterfuntimeiterfuntimeiterfuntimeheart27013290.380 30.09300.380 30.13310.380 30.19colon-cancer622 000850.200 71.05900.200 51.251090.200 51.68diabetes7688770.609 90.981700.609 91.812190.609 94.30pyrim7427410.218 30.06430.218 30.09510.218 30.12splice1 00060510.372 81.01590.372 91.231730.372 83.55ionosphere35134550.370 40.33650.370 40.61720.370 41.08a2a2 2651231340.353 39.661620.353 511.342110.353 615.57german.numer1 00024400.476 70.66510.476 70.77600.476 71.48australian69014530.336 70.53640.336 70.881100.336 71.11triazines18660620.128 80.24420.128 80.19400.128 80.28svmguide31 24321940.504 21.94960.504 42.181650.504 15.96fourclass862260.533 70.0970.533 70.11180.537 70.25breast-cancer68310280.010 30.25300.010 30.35330.010 30.75sonar208601010.472 70.481330.472 40.641440.472 70.91

表3 λ=5×10-4，=10-4的比較結(jié)果

表3 λ=5×10-4，=10-4的比較結(jié)果

數(shù)據(jù)集HZ_NBBHLBBASFISTAdatasetmniterfuntimeiterfuntimeiterfuntimeheart27013140.356 50.05180.356 60.08180.356 50.11colon-cancer622 0001160.014 41.251260.013 81.391200.015 01.94diabetes7688160.623 40.17200.624 20.151260.624 22.56pyrim7427320.017 60.03410.017 60.06410.017 60.07splice1 00060300.372 50.61330.368 70.68880.368 13.61ionosphere35134410.311 80.24460.313 90.32570.312 10.41a2a2 265123260.359 81.63300.359 41.83720.359 84.42german.numer1 00024230.473 00.29250.473 50.32280.473 60.88australian69014220.331 40.23300.330 10.33440.327 90.83triazines18660440.026 20.14260.026 30.08400.026 80.22svmguide31 24321270.502 40.47320.503 80.56820.502 52.84fourclass862250.531 60.0560.531 60.07150.531 60.11breast-cancer68310200.006 00.17260.006 10.23340.006 10.55sonar20860490.315 10.17830.302 30.312060.302 11.41

表4 λ=5×10-4，=10-6的比較結(jié)果

表4 λ=5×10-4，=10-6的比較結(jié)果

數(shù)據(jù)集HZ_NBBHLBBASFISTAdatasetmniterfuntimeiterfuntimeiterfuntimeheart27013300.356 30.09340.356 30.13310.356 30.20colon-cancer622 0002440.013 02.382630.013 12.771500.013 12.91diabetes7688640.610 90.611640.610 21.622180.611 44.17pyrim7427470.017 60.05550.017 60.09660.017 80.09splice1 00060610.367 81.22540.367 81.081760.367 85.66ionosphere35134710.311 20.391260.311 20.89890.311 30.67a2a2 2651231830.355 310.051450.355 88.861500.355 317.66german.numer1 00024410.472 70.58480.472 70.71610.472 71.79australian69014590.327 30.61640.327 30.58700.327 31.22triazines18660480.026 20.14390.026 20.16430.026 80.23svmguide31 243211000.496 21.931300.496 62.561740.496 35.33fourclass862260.531 60.0770.531 60.09180.531 60.29breast-cancer68310380.006 00.31380.006 00.35540.006 00.88sonar208602270.269 80.922460.273 71.232730.269 21.89

2.2 圖像去模糊問題

在本小節(jié)中，測試了圖像去模糊問題，測試問題具有以下形式：

其中A=RW，R表示模糊算子矩陣，W表示反正交Haar小波變換，x為原始圖像，y表示模糊的觀測圖。類似于文獻(xiàn)[9]中的圖像反卷積實(shí)驗(yàn)，考慮了表5中的三個(gè)標(biāo)準(zhǔn)的基準(zhǔn)問題，測試圖像是256×256像素的Cameraman圖像(如表6所示)和512×512像素的Lena圖像(如表7所示)，并將HZ_NBB算法與SpaRSA[6]、AM_GPSR[17]和CPGA[2]算法進(jìn)行比較。AM_GPSR是一種基于動(dòng)量加速的梯度投影算法，CPGA則是一種控制步長的臨近梯度算法。三個(gè)實(shí)驗(yàn)的正則化參數(shù)λ分別取 0.01、0.25和0.5。我們使用PSNR(峰值信噪比)來比較算法的圖像去模糊性能，所有測試算法的停止條件使用(21)式，我們令=10-5。

表5 圖像去模糊實(shí)驗(yàn)

表6 Cameraman圖像結(jié)果

表7 Lena圖像結(jié)果

表6和表7給出了所有測試問題的數(shù)值結(jié)果，從表6可以看到，對于Cameraman圖像，HZ_NBB算法解決所有問題的CPU時(shí)間和迭代次數(shù)都是最少的，并且HZ_NBB算法比SpaRSA、AM_GPSR和CPGA算法獲得了更好的PSNR值。從表7可以看到，對于Lena 圖像，HZ_NBB算法對于所有問題的CPU時(shí)間和迭代次數(shù)都是最少的，對于實(shí)驗(yàn)1和3，HZ_NBB得到了最大的PSNR值，而實(shí)驗(yàn)2，SpaRSA得到了最大的PSNR值，圖1和圖2分別給出了對表5中實(shí)驗(yàn)1的圖像去模糊結(jié)果。數(shù)值結(jié)果表明，所提出的算法是有效的。

圖1 表5中問題1的Cameraman圖像去模糊結(jié)果

圖2 表5中問題1的Lena圖像去模糊結(jié)果

3 結(jié)語

在本文中，使用一種新的BB步長結(jié)合非單調(diào)線搜索技術(shù)，提出了一種用于求解結(jié)構(gòu)組合優(yōu)化問題的BB型方法，在適當(dāng)?shù)臈l件下，證明了所提出算法的全局收斂性。在第2節(jié)中，將所提出的算法應(yīng)用于1正則化邏輯回歸問題和圖像去模糊問題中，并與其他算法進(jìn)行了數(shù)值比較，結(jié)果表明，相比于已有的算法，本文的算法使用了更少的CPU時(shí)間以及更少的迭代次數(shù)，數(shù)值性能上是更有優(yōu)的。