基于ADMM算法正則化最優(yōu)步長的研究

陳慶國,趙建偉,曹飛龍

(中國計(jì)量大學(xué) 理學(xué)院,浙江 杭州 310018)

基于ADMM算法正則化最優(yōu)步長的研究

陳慶國,趙建偉,曹飛龍*

(中國計(jì)量大學(xué) 理學(xué)院,浙江 杭州 310018)

交替方向乘子法(Alternating Direction Method of Multipliers,簡稱ADMM)已經(jīng)成為求解大規(guī)模結(jié)構(gòu)性優(yōu)化問題的有效方法。盡管已經(jīng)有較多關(guān)于ADMM算法收斂性的研究,但關(guān)于該算法參數(shù)對(duì)收斂性影響的定量表示仍須進(jìn)一步研究,已有的結(jié)果中僅是在實(shí)驗(yàn)中憑經(jīng)驗(yàn)對(duì)步長進(jìn)行選取。文章研究ADMM算法l1正則化最小的一個(gè)重要問題Lasso的收斂因子。研究發(fā)現(xiàn)解的形式可用軟閾值算子表示,分析發(fā)現(xiàn)軟閾值的三種情況可以等價(jià)轉(zhuǎn)化成算法收斂因子的兩種情況,然后通過最小化收斂因子解出最優(yōu)的步長。實(shí)驗(yàn)表明,應(yīng)用該方法選出的步長,其相應(yīng)算法的收斂速度明顯快于其他選取步長的情況。此外,將該方法應(yīng)用到壓縮感知問題,給出了一個(gè)計(jì)算最優(yōu)步長的近似值策略,獲得了較好的實(shí)驗(yàn)效果。

交替方向乘子法;收斂速率;最優(yōu)步長;最優(yōu)算法;壓縮感知

0 引言

利用交替方向乘子法(Alternating Direction Method of Multipliers,簡稱 ADMM)求解結(jié)構(gòu)化的凸優(yōu)化問題是十分有效的。該方法早在20世紀(jì)70年代就已經(jīng)被提出,類似的思想可追溯到五十年代中期[1]。從數(shù)學(xué)上講,ADMM既有乘子法的強(qiáng)收斂性質(zhì)又有對(duì)偶上升法的分解性。因此,該方法比較適合求解大規(guī)模的優(yōu)化問題。至今,該方法已經(jīng)在諸多領(lǐng)域得到廣泛應(yīng)用,如壓縮感知[2]、正則化估計(jì)[3]、圖像處理[4]、機(jī)器學(xué)習(xí)[5]和無線傳感網(wǎng)絡(luò)資源分配[6]等。對(duì)偶分解是一個(gè)經(jīng)典的數(shù)學(xué)思想,可以追溯到20世紀(jì)60年代早期[1]。因其在求解大規(guī)模的線性問題上十分有效而被人們熟知[7-8],主要用來產(chǎn)生并行化的算法。如果優(yōu)化問題結(jié)構(gòu)合理,應(yīng)用對(duì)偶分解技術(shù),原問題則可以在多個(gè)處理器上應(yīng)用梯度下降法或次梯度法進(jìn)行分布式計(jì)算,從而得到一個(gè)全局最優(yōu)解。如果問題的參數(shù)如損失函數(shù)的利普希茲(Lipschitz)常數(shù)可知,則最優(yōu)步長和相關(guān)的收斂性是可知的[9]。然而,梯度法存在缺點(diǎn),即它對(duì)步長的選擇非常敏感,選擇不合適的步長甚至?xí)?dǎo)致算法不收斂。

然而,ADMM對(duì)步長具有較強(qiáng)的魯棒性。在一定的條件下,該方法能保證對(duì)所有的步長都收斂。近來,為了研究ADMM算法的收斂速率,人們做了很多工作。文獻(xiàn)[10]指出,如果目標(biāo)函數(shù)是強(qiáng)凸的并且具有利普希茲連續(xù)梯度,那么由ADMM算法產(chǎn)生的迭代在一定距離度量內(nèi)可以線性收斂到最優(yōu)解。需要強(qiáng)調(diào)的是,雖然ADMM算法具有線性收斂速率,但是收斂所需迭代次數(shù)或者收斂時(shí)間仍然嚴(yán)重依賴于算法的步長。本文將展示選擇一個(gè)較差的步長將會(huì)導(dǎo)致ADMM算法收斂需要較長的時(shí)間。一些最近的論文研究了關(guān)于分布式凸優(yōu)化問題ADMM算法的最優(yōu)步長選擇問題,如文獻(xiàn)[11-12]。文獻(xiàn)[10]給出了當(dāng)目標(biāo)函數(shù)是強(qiáng)凸且具有利普希茲連續(xù)梯度時(shí)的推薦步長,文獻(xiàn)[13]首次給出了ADMM求解二次規(guī)劃問題最優(yōu)步長的選擇方法,結(jié)果更加精確,但該方法要求約束矩陣行滿秩,這給實(shí)際應(yīng)用帶來了一定的限制。文獻(xiàn)[14]對(duì)文獻(xiàn)[13]的方法做了改進(jìn),不再需要約束矩陣滿足行滿秩這一條件,并給出了最優(yōu)步長并證明了算法的收斂性。

就我們所知,至今尚無關(guān)于l1正則化ADMM算法的最優(yōu)步長的研究,受文獻(xiàn)[13]的啟發(fā),對(duì)于Lasso問題,在一定的條件下,對(duì)軟閾值的分段分析發(fā)現(xiàn),對(duì)應(yīng)的收斂因子只有兩種情況。通過最小化ADMM迭代算法的收斂因子,計(jì)算出使收斂因子最小的步長,此時(shí)算法收斂速度最快。實(shí)驗(yàn)結(jié)果表明,相對(duì)于經(jīng)驗(yàn)性選擇的步長,我們的方法所給出的最優(yōu)步長大大加快了ADMM算法的收斂速度,這對(duì)類似的實(shí)驗(yàn)步長的選擇都具有指導(dǎo)意義。

文中符號(hào)說明:我們定義R為實(shí)數(shù)集,I是單位矩陣,所有的向量都是列向量,給定一個(gè)矩陣A∈Rm×n,AT表示矩陣A的轉(zhuǎn)置矩陣,對(duì)于一個(gè)方陣B∈Rn×n,λi(B)表示矩陣B的第i個(gè)特征值,λmax(B)和λmin(B)分別表示矩陣B的最大特征值和最小特征值。

1 壓縮感知背景和ADMM算法

1.1 壓縮感知

利用壓縮感知成功重構(gòu)稀疏信號(hào)有兩個(gè)關(guān)鍵要素,一個(gè)是傳感矩陣;另一個(gè)是信號(hào)重構(gòu)算法[15]。傳感矩陣A須包含足夠的原始稀疏信號(hào)的信息,Candès和Tao證明了傳感矩陣必須滿足約束等距性條件[16],Baraniuk在文獻(xiàn)[17]中給出約束等距性的等價(jià)條件是測量矩陣和稀疏表示的基不相關(guān),文獻(xiàn)[16]、[18]證明了當(dāng)測量矩陣是高斯隨機(jī)矩陣時(shí),傳感矩陣能以較大概率滿足約束等距性條件。壓縮感知的核心是信號(hào)重建算法,Candès等人證明信號(hào)重建問題可以通過求解如下l0范數(shù)問題解決[16],

min ‖x‖0

s.t.Ax=b.

但最小l0范數(shù)問題是一個(gè)NP-hard問題[19]。研究人員提出了一系列求得次優(yōu)解的算法,其中一個(gè)方法是把l0范數(shù)替換為l1范數(shù)[20]:

min ‖x‖1

s.t.Ax=b.

文獻(xiàn)[21-22]證明了在一定條件下,二者是等價(jià)的,其中A∈Rm×n(m?n)是觀測矩陣,要求滿足約束等距性條件,一般為高斯矩陣,本文的實(shí)驗(yàn)也是選擇高斯矩陣作為觀測矩陣,y∈Rm是觀測向量,x∈Rn是待重構(gòu)的信號(hào)。引入重構(gòu)誤差,上述問題轉(zhuǎn)化為

min ‖x‖1

s.t. ‖Ax-b‖2≤ε.

1.2 ADMM算法

ADMM算法主要用于解決如下形式的優(yōu)化問題:

minf(x)+g(z)

s.t.Ax+Bz=c,

(1)

其中f和g都是凸函數(shù),x∈Rn,z∈Rm,A∈Rp×n,B∈Rp×m,c∈Rp,一般地,f是損失函數(shù),g是正則項(xiàng),更詳細(xì)的說明可見文獻(xiàn)[1]。求解該優(yōu)化問題主要依靠其增廣拉格朗日函數(shù):

由此,按順序更新變量x和變量z,然后再更新對(duì)偶變量:

μk+1=μk+ρ(Axk+1+Bzk+1-c).

(2)

uk+1=uk+Axk+1+Bzk+1-c.

(3)

當(dāng)變量x和z的更新能很有效地計(jì)算時(shí),例如它們具有封閉形式的解,那么整個(gè)ADMM算法是非常有用的。具有封閉形式的解的情形有線性和二次規(guī)劃、基追蹤、l1正則化最小問題、模型擬合等,完整的討論見文獻(xiàn)[1]。ADMM算法的優(yōu)點(diǎn)是僅有一個(gè)參數(shù)ρ,并且在一定的條件下,該方法對(duì)任意參數(shù)均收斂[23]。正如我們?cè)诘谝还?jié)中所說,ADMM算法與梯度法形成對(duì)比,如果步長參數(shù)選擇得太大,則梯度法會(huì)發(fā)散。盡管如此,步長依然對(duì)ADMM算法的收斂因子有直接影響。ADMM的收斂性用殘差來刻畫,原始?xì)埐詈蛯?duì)偶?xì)埐罘謩e是

rk+1=Axk+1+Bzk+1-c

sk+1=ρATB(zk+1-zk).

下面我們討論某些情況下ADMM算法的收斂性并推導(dǎo)出使收斂因子最小的步長的顯式表達(dá)式。

2 l1正則化最小問題的最優(yōu)收斂因子

在統(tǒng)計(jì)學(xué)、機(jī)器學(xué)習(xí)和控制論中,正則化估計(jì)問題是極其常見的,一般

minf(x)+λg(x),

(4)

其中損失函數(shù)f(x)可以是任意的凸函數(shù),后一項(xiàng)g(x)是正則項(xiàng),λ是正則化參數(shù)且大于0,加入正則項(xiàng)的目的一般是為了防止過擬合,常見的有l(wèi)1正則項(xiàng)和l2正則項(xiàng),l1正則項(xiàng)使解具有稀疏性,這種稀疏性十分重要。在機(jī)器學(xué)習(xí)等領(lǐng)域中,稀疏性問題隨處可見,當(dāng)(4)式的正則項(xiàng)是l1正則項(xiàng)時(shí),它的一個(gè)重要特例是l1正則線性回歸,也叫Lasso問題,關(guān)于Lasso問題更詳細(xì)的背景可以查看文獻(xiàn)[24-25],具體如下:

(5)

其中A∈Rm×n,b∈Rm,把上面的Lasso問題寫成ADMM形式:

minf(x)+g(z)

s.t.x-z=0,

xk+1=(ATA+ρI)-1(ATb+ρ(zk-uk))

uk+1=uk+xk+1-zk+1,

(6)

其中zk+1是軟閾值形式的解,軟閾值算子S的定義為

這說明軟閾值算子是一個(gè)收縮算子。為方便后面的計(jì)算,根據(jù)上面軟閾值算子的定義,把zk+1的解寫成如下分段形式:

(7)

(8)

令z*是該問題的不動(dòng)點(diǎn),即z*=Ez*+C,那么對(duì)偶誤差ek+1=zk+1-z*,即

ek+1=Eek.

(9)

對(duì)偶誤差收斂當(dāng)且僅當(dāng)矩陣E的譜半徑小于1,為了表示E的特征值,令λi(ATA)為ATA的特征值,則E的特征值為:

(10)

很明顯,當(dāng)ATA的特征值大于零時(shí),此時(shí)(10)式是小于1的,算法是收斂的。因此,求解最優(yōu)的步長等價(jià)于求解如下的優(yōu)化問題:

(11)

從(10)式可知,ζ(ρ,λi(ATA))關(guān)于λi(ATA)是單調(diào)遞減的,所以有

(12)

我們暫不做進(jìn)一步處理,先考慮第二種和第三種情況下最優(yōu)步長的結(jié)果。

當(dāng)zk+1的迭代從開始到收斂都是(7)式中的第二種情況時(shí),把zk+1=0代入到(6)式中,

(13)

類似于上面的做法,此時(shí)算法收斂當(dāng)且僅當(dāng)矩陣E的譜半徑小于1,令λi(ATA)為ATA的特征值,此時(shí)E的特征值為:

(14)

同樣地,當(dāng)ATA的特征值都大于零時(shí),(14)式是恒小于1的,求解最優(yōu)的步長等價(jià)于求解如下的優(yōu)化問題:

(15)

由(14)式可知,此時(shí)ζ(ρ,λi(ATA))關(guān)于λi(ATA)是單調(diào)遞增的,所以(15)式可以寫成

(16)

該結(jié)果類似于第一種情況的(12)式。

(17)

最終的求解最優(yōu)步長的優(yōu)化問題:

(18)

(19)

即z等于零和不等于零的情況,對(duì)應(yīng)的矩陣E的譜半徑為

(20)

(21)

對(duì)應(yīng)的收斂因子:

(22)

3 實(shí)驗(yàn)

3.1 Lasso問題

為驗(yàn)證本文結(jié)論的正確性,我們先考慮一個(gè)l1正則最小問題,給出最優(yōu)步長和收斂性情況。模型為(5)式,其中

當(dāng)選取最優(yōu)的步長時(shí),ADMM算法迭代13次達(dá)到收斂,表1給出了迭代過程中z的值,此時(shí)向量z是三維的,迭代次數(shù)為1時(shí)z=0表示初始值選取零向量。在后續(xù)整個(gè)迭代中,z1和z3都不等于零,說明它們是按照(16)式的第一種情況更新的,z2在整個(gè)迭代中幾乎都等于零,有一步迭代不等于零,整個(gè)算法的迭代方式與我們之前的假設(shè)相符,圖1中的理論最優(yōu)步長和實(shí)際結(jié)果也相符,這也驗(yàn)證了第三節(jié)方法的正確性。

Fig.1 Iterative results圖1 迭代結(jié)果

Fig.2 Convergence of the optimal step size圖2 最優(yōu)步長時(shí)算法的收斂情況

表1 步長最優(yōu)時(shí),迭代到收斂的z的值Table 1 Iteration value of z when the step size is optimal

3.2 壓縮感知應(yīng)用

下面在壓縮感知背景下測試本文所提出的方法,A∈Rm×n,m=1 500,n=5 000,觀測矩陣A服從均值為0、方差為1的高斯分布。選擇觀測矩陣為高斯矩陣,待恢復(fù)信號(hào)的稀疏度比p=0.02。此時(shí),矩陣A不再是列滿秩矩陣,ATA的特征值中前(n-m)個(gè)元素都為0。為了保證算法收斂,λmin(ATA)用ATA的特征值的最小非零元來代替,得到一個(gè)理論最優(yōu)值的近似,圖3橫坐標(biāo)是步長,縱坐標(biāo)是算法收斂時(shí)的迭代次數(shù),紅線所示ρ*=2.34是理論值,觀察可以看到在此位置藍(lán)色曲線也是最低點(diǎn),也正是收斂所需的實(shí)際最少迭代次數(shù)的步長。此時(shí)信號(hào)長度為5 000,稀疏度為100,這說明4 900個(gè)元素最后都為0,也就是說它們?cè)谑諗繒r(shí)的迭代公式都是(19)式zk+1=0,在迭代過程中總是會(huì)出現(xiàn)不等于零的情況。同樣地,100個(gè)非零元素在收斂時(shí)等于零,但在迭代過程中,會(huì)出現(xiàn)等于零的情況。總的來說,這符合上面的假設(shè)條件,所以理論最優(yōu)步長的近似和實(shí)際最優(yōu)值相吻合。

本文算法對(duì)應(yīng)的收斂條件是對(duì)偶誤差與原始誤差的和不超過10-5,圖4展示了最優(yōu)步長和其他步長時(shí)的收斂情況,最優(yōu)步長只需要30次迭代達(dá)到收斂,收斂速度明顯快于其他步長。從圖上來看,當(dāng)步長選擇過小時(shí),算法收斂需要更多的迭代次數(shù),這是因?yàn)檫^小的步長需要更多的迭代次數(shù)才能到達(dá)最優(yōu)解。當(dāng)步長選擇過大時(shí),同樣會(huì)需要較多的迭代次數(shù),因?yàn)橛锌赡軙?huì)走過最優(yōu)解,從而“回頭”繼續(xù)尋找,可能需要反復(fù)多次尋找才能找到最優(yōu)解。特別注意的是當(dāng)步長為1時(shí),這也是很多實(shí)驗(yàn)的經(jīng)驗(yàn)選擇,而本實(shí)驗(yàn)結(jié)果表明它并不是最好的。在圖4中,盡管在前10次迭代中,步長為1時(shí)的收斂速度要快于最優(yōu)步長的情形,但從后續(xù)的迭代直到收斂這一過程,最優(yōu)步長的收斂速度遠(yuǎn)快于步長為1的情況,也遠(yuǎn)快于其他步長的情況,且最先達(dá)到收斂,說明最優(yōu)步長的收斂速度快于一般的默認(rèn)步長。圖5則是局部細(xì)節(jié)圖,更加直觀。

Fig.3 Optimal step size in the compression sensor圖3 壓縮感知背景下的最優(yōu)步長

Fig.4 Number of convergence iterations under different steps圖4 不同步長下的ADMM算法的收斂速度

Fig.5 Local details of figure 4圖5 圖4局部細(xì)節(jié)

3.3 考慮稀疏度比的變化

鑒于壓縮感知針對(duì)稀疏信號(hào)重構(gòu)問題。信號(hào)的稀疏性變化,對(duì)應(yīng)的迭代步長如何變化,是一個(gè)值得研究的問題。根據(jù)第三節(jié)的推導(dǎo),信號(hào)稀疏度越大,則說明向量z更新的情況更多的是(19)式第二種情況。取觀測矩陣為A∈R550×1 000且是高斯矩陣,在其它條件不變,不同稀疏度比例的情況下,圖6展示了最優(yōu)步長和迭代次數(shù)的關(guān)系。橫坐標(biāo)是步長,縱坐標(biāo)是迭代次數(shù),其中任意一條曲線表示選擇對(duì)應(yīng)稀疏度比時(shí),不同步長下算法達(dá)到收斂時(shí)所需迭代次數(shù)。通過分析圖6,我們發(fā)現(xiàn)在8種不同稀疏度比中,它們的最優(yōu)步長沒有變化,即這些曲線的最低點(diǎn)相同,并且是8條曲線的最低點(diǎn),對(duì)應(yīng)的理論最優(yōu)值也重疊在了一起,如圖6中所指豎線,它們的不同體現(xiàn)在當(dāng)步長選擇偏大時(shí),對(duì)應(yīng)的迭代次數(shù)不同。這也可以解釋,根據(jù)上一節(jié)提出的最優(yōu)步長的理論,最優(yōu)步長只跟觀測矩陣有關(guān),信號(hào)的稀疏度并不影響結(jié)果,圖6的結(jié)果證明了這一點(diǎn)。

Fig.6 Optimal step size of ADMM under different sparse degree ratio圖6 不同稀疏度比下ADMM算法的最優(yōu)步長

4 結(jié)論

本文研究了ADMM算法關(guān)于Lasso問題的最優(yōu)步長問題。對(duì)軟閾值算子進(jìn)行分析,發(fā)現(xiàn)對(duì)應(yīng)的收斂因子可以簡化成兩種情況,推導(dǎo)出算法的收斂因子,通過最小化收斂因子給出使算法收斂速度最快的參數(shù)的顯示表達(dá)式,我們用數(shù)值仿真實(shí)驗(yàn)驗(yàn)證了分析結(jié)果。當(dāng)本文方法應(yīng)用到壓縮感知問題時(shí),由于觀測矩陣A不是列滿秩的,λmin(ATA)等于零,這會(huì)導(dǎo)致算法不收斂。為了解決這個(gè)問題,我們用ATA的特征值的最小非零元來代替λmin(ATA),這樣保證了算法的收斂性,雖然得到的步長只是最優(yōu)值的近似,但實(shí)驗(yàn)表明此時(shí)算法收斂的速度仍然明顯快于其他步長的情形。最后做了改變信號(hào)稀疏度的實(shí)驗(yàn),最優(yōu)步長的選擇并沒有改變,與上述結(jié)果相符。本文提出的針對(duì)l1正則最小問題的ADMM算法的步長選擇方法簡單且有效,因?yàn)榻?jīng)驗(yàn)性的選取步長往往不是最優(yōu)的,本文的方法能準(zhǔn)確找到最優(yōu)步長,對(duì)類似的實(shí)驗(yàn)都具有一定的指導(dǎo)意義。

本文一個(gè)可以改進(jìn)的地方是,在壓縮感知的背景下,觀測矩陣A∈Rm×n的行數(shù)遠(yuǎn)小于列數(shù),即觀測次數(shù)遠(yuǎn)小于稀疏信號(hào)長度,此時(shí)ATA的前(n-m)個(gè)特征值都是0,而λmin(ATA)不能等于零,我們用最小非零元來替代,得到一個(gè)最優(yōu)解的近似,盡管這個(gè)近似解效果也較好,但我們認(rèn)為是可以得到準(zhǔn)確的最優(yōu)步長的,如何解決這個(gè)問題是需要進(jìn)一步研究的。

[1] Boyd S,Parikh N,Chu E,etal.Distributed Optimization and Statistical Learning Via the Alternating Direction Method of Multipliers[J].FoundationsandTrendsinMachineLearning,2011,3(1):1-122.DOI:10.1561/2200000016.

[2] Yang J,Zhang Y.Alternating Direction Algorithms forl1-problems Incompressive Sensing[J].SIAMJournalonScientificComputing,2011,33(1):250-278.DOI:10.1137/090777761.

[3] Wahlberg B,Boyd S,Annergren M,etal.An ADMM Algorithm for a Class of Total Variation Regularized Estimation Problems[C]∥Proc. 16th IFAC Symposium on System identification,Brussels,Belgium,IFAC Proceedings Volumes:2012,45(16):83-88.DOI:10.3182/20120711-3-BE-2027.00310.

[4] Figueiredo M,Bioucas-Dias J.Restoration of Poissonian Imagesusing Alternating Direction Optimization[J].IEEETransImageProcessing,2010,19(12):3133-3145.DOI:10.3182/20120711-3-BE-2027.00310.

[5] Forero P A,Cano A,Giannakis G B.Consensus-based Distributed Linear Support Vector Machines[C]∥Proceeding IPSN’10 proceeding of the 9th ACM/IEEE International Conference on Information Processing in Sensor Networks,2010:35-46.DOI:10.1145/1791212.1791218.

[6] Joshi S,Codreanu M,Latva-aho M.Distributed Resource Allocation for MISO Downlink Systems Via the Alternating Direction Method of Multipliers[J].EURASIPJournalonWirelessCommunicationsandNetworking,2014,2014(1).DOI:10.1186/1687-1499-2014-1.

[7] Benders J F.Partitioning Procedures for Solving Mixed-variables Programming Problems[J].NumerischeMathematik,1962,4(1):238-252.DOI:10.1007/bf01386316.

[8] Dantzig G B,Wolfe P.Decomposition Principle for Linear Programs[J].OperationsResearch,1960,8(1):101-111.DOI:10.1287/opre.8.1.101.

[9] Nesterov Y.Introductory Lectures on Convex Optimization:A Basic Course[J].AppliedOptimization,2004，85(5)：ⅹⅷ，236.DOI:10.1007/978-1-4419-8853-9.

[10] Deng W，Yin W.On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers[J].JournalofScientificComputing,2015,66(3):889-916.DOI:10.1007/s10915-015-0048-x.

[11] Teixeira A,Ghadimi E,Shames I,etal.Optimal Scaling of the ADMM Algorithm for Distributed Quadratic Programming[C]∥Proc.52nd IEEE Conference on Decision Control (CDC).Florence,Italy:IEEE,2013.DOI:10.1109/CDC.2013.6760977.

[12] Shi W,Ling Q,Yuan K,etal.On the Linear Convergence of the ADMM in Decentralized Consensus Optimization[J].IEEETransactionsonSignalProcessing,2014,62(7):1750-1761.DOI:10.1109/tsp.2014.2304432.

[13] Ghadimi E,Teixeira A,Shames I,etal.Optimal Parameter Selection for the Alternating Direction Method of Multipliers(ADMM):Quadratic Problems[J].IEEETransactiononAutomaticControl,2015,60(3):644-658.DOI:10.1109/tac.2014.2354892.

[14] Raghunathan A U，Cairano S D.Alternating Direction Method of Multipliers for Strictly Convex Quadratic Problems:Optimal Parameter Selection[C]∥American Control Conference(ACC).2014:4324-4329.DOI:10.1109/acc.2014.6859-093.

[15] 李樹濤,魏丹.壓縮傳感綜述[J].自動(dòng)化學(xué)報(bào),2009,35(11):1369-1377.

[16] Candès E J,Tao T.Decoding by Linear Programming[J].IEEETransactionsonInformationTheory,2005,51(12):4203-4215.DOI:10.1109/tit.2005.858979.

[17] Baraniuk R G.Compressive Sensing[J].IEEESignalProcessingMagazine,2007,24(4):118-121.DOI:10.1109/MSP.2007.4286571.

[18] Candès E J,Romberg J,Tao T.Stable Signal Recovery From in Complete and Inaccurate Measurements[J].CommunicationsononPureandAppliedMathematics,2006,59(8):1207-1223.DOI:10.1002/cpa.20124.

[19] Donoho D L.For Most Large Underdetermined Systems of Linear Equations,the Minimall1Norm Solution is Also the Sparsest Solution[J].CommunicationsonPureandAppliedMathematics,2006,59(6):797-829.DOI:10.1002/cpa.20132.

[20] Candès E J,Romberg J,Tao T.Robust Uncertainty Principles:Exact Signal Reconstruction from Highly Incomplete Frequency Information[J].IEEETransactionsonInformationTheory,2006,52(2):489-509.DOI:10.1109/tit.2005.862083.

[21] Chen S B,Donoho D L,Saunders M A.Atomic Decomposition by Basis Pursuit[J].SIAMJournalonScientificComputing,1998,20(1):33-61.DOI:10.1137/s1064827596304010.

[22] Donoho D L,Elad M,Temlyakov V N.Stable Recovery of Sparse Over Complete Representations in the Presence of Noise[J].IEEETransactionsonInformationTheory,2006,52(1):6-18.DOI:10.1109/tit.2005.860430.

[23] Eckstein J,Yao W.Augmented Lagrangian and Alternating Direction Methods for Convex Optimization:A Tutorial and Some Illustrative Computational Results[R].RUTCOR Research Reports 32:2012.

[24] Hastie T,Tibshirani R,Friedman J.The Elements of Statistical Learning:Data Mining,Inference and Prediction.Springer,second ed,2009.

[25] Tibshirani R.Regression Shrinkage and Selection Via the Lasso:a Retrospective[J].JournaloftheRoyalStatisticalSociety:SeriesB(StatisticalMethodology)，2011,73(2):273-282.DOI:10.1111/j.1467-9868.2011.00771.x.

ResearchOnRegularizationOptimalStepSizeofADMMAlgorithm

CHEN Qingguo,ZHAO Jianwei,CAO Feilong*

(CollegeofScience,ChinaJiliangUniversity,Hangzhou310018,China)

The alternative direction method of multipliers (ADMM) has become an effective method to solve large-scale structural optimization problems.Although there are many studies on the convergence of the ADMM algorithm, the quantitative expression of the impact of the algorithm parameters on the convergence still needs to be further studied. It is only in the experiment that the step size is selected empirically.We study the convergence of Lasso which is an important problem ofl1regularized minimization.The results indicated that the form of the solution can be expressed by soft thresholding operator, and the three cases of soft thresholds can be equivalently transformed into two cases of algorithm convergence factor. The optimal step size is then solved by minimizing the convergence factor.The experimental results show that the convergence rate of the proposed algorithm is faster than that of other steps.In addition, when the method is applied to the problem of compressive sensing, an approximate strategy for calculating the optimal step size is given, and a better experimental result is obtained.

ADMM;convergence rate;optimal step-size;optimal algorithm; compressive sensing

10.13451/j.cnki.shanxi.univ(nat.sci.).2017.04.001

2017-04-12；

2017-05-26

國家自然科學(xué)基金(61672477；61571510)

陳慶國(1992-)，男，碩士研究生，研究方向：分布式算法。E-mail:1014115430@qq.com

*通信作者：曹飛龍(CAO Feilong)，E-mail:flcao@cjlu.edu.cn

TP391

A

0253-2395(2017)04-0661-09