基于對(duì)偶的不精確交替方向乘子法求解核范數(shù)正則化最小二乘問(wèn)題

史冰冰, 王青松

(1.西南交通大學(xué)數(shù)學(xué)學(xué)院,四川成都611731;2.北京航空航天大學(xué)數(shù)學(xué)科學(xué)學(xué)院,北京100191)

§1 背景簡(jiǎn)介

核范數(shù)正則化最小二乘問(wèn)題來(lái)源于仿射秩最小化問(wèn)題,而秩最小化本質(zhì)為矩陣補(bǔ)問(wèn)題,即通過(guò)矩陣的一部分信息,求解整個(gè)矩陣信息對(duì)其補(bǔ)充.矩陣秩最小化在圖像恢復(fù),圖像去光照影響,圖像矯正與去噪及智能系統(tǒng)推薦等各個(gè)領(lǐng)域取得了相應(yīng)的成果.

可以通過(guò)求解以下優(yōu)化問(wèn)題恢復(fù)秩為r的大多數(shù)矩陣M:

其中M∈Rn×n,并且該矩陣有m個(gè)采樣項(xiàng)Mij:(i,j)∈?,其中?是基數(shù)m的隨機(jī)子集.然而問(wèn)題(1)通常是NP難的非凸優(yōu)化問(wèn)題,[1]證明了經(jīng)過(guò)突松弛最小化了核范數(shù),進(jìn)而將問(wèn)題轉(zhuǎn)化為:

此處考慮更一般的形式[2]:

若從問(wèn)題(1.1)的約束角度考慮,Fazel[3]和Boyd[4]對(duì)仿射秩最小化問(wèn)題做凸松弛轉(zhuǎn)化為以上核范數(shù)問(wèn)題(3).此類一般約束形式的核范數(shù)最小化問(wèn)題早已在各個(gè)領(lǐng)域得到充分發(fā)展,包括機(jī)器學(xué)習(xí)[5-6],控制問(wèn)題[4,7-8]以及歐幾里德嵌入[9]等.

但是實(shí)際觀測(cè)到的b往往帶有噪聲,那么A(X)=b可能是不可行的,必須放寬該約束.因此尋求最小化殘差||A(X)?b||2,并考慮如下核規(guī)范正則化最小二乘問(wèn)題[10],即:

其中A:Rp×q→Rm是一個(gè)線性映射,||X||?是跡范數(shù)(也被稱為核范數(shù))為矩陣X的所有奇異值之和,%>0為正則化參數(shù),b∈Rm.

針對(duì)問(wèn)題(4)已經(jīng)有很多種求解方法.根據(jù)[11]的工作,問(wèn)題(4)可以等價(jià)轉(zhuǎn)化為半正定規(guī)劃問(wèn)題(Semidefinite Programming Problem(SDP)),用求解SDP的方法來(lái)求解,比如[12-13].然而,這些求解器不適用于p,q規(guī)模較大的問(wèn)題,因?yàn)樵谶@些求解器的每次迭代中,即使數(shù)據(jù)稀疏也必須求解大規(guī)模的線性方程.

為了克服求解SDP的缺陷,最近也出現(xiàn)很多方法.Cai[2]等人提出的奇異值閾值算法求解(3)的相似模型,即

其中τ>0為給定的參數(shù),||X||F表示矩陣X的Frobenius范數(shù).

最近Ma等人[14]通過(guò)逼近奇異值分解過(guò)程提出了固定點(diǎn)連續(xù)算法(Fixed Point Continuation with Approximate SVD)用以求解(4).另外Chen[15]等人利用交替方向法求解類似(2)的帶有噪音的矩陣完備化問(wèn)題,經(jīng)過(guò)對(duì)問(wèn)題形式轉(zhuǎn)換分解為可分割的兩項(xiàng)交替求解.

Toh和Yun[16]提出了一種加速的臨近梯度法來(lái)求解問(wèn)題(4),該文章的工作中通過(guò)線性搜索來(lái)加速算法收斂速度,但是在做線性搜索時(shí)需要隨時(shí)注意參數(shù)的選擇,以使得不至于步長(zhǎng)過(guò)小而收斂速度變慢.本文將考慮從問(wèn)題(4)的對(duì)偶形式出發(fā)利用交替方向乘子法求解該問(wèn)題.

§2 預(yù)備知識(shí)

2.1 基本概念及符號(hào)說(shuō)明

本節(jié)來(lái)說(shuō)明優(yōu)化中常用的一些符號(hào)以及概念[17].

1)若H1和H2是希爾伯特空間,A:H1yH2是一個(gè)有界線性算子,如果算子A?:H2yH1,對(duì)于所有的x∈H1,y∈H2,滿足:hAx,yi=hx,A?yi則稱A?為A的希爾伯特伴隨(共軛)算子.

2)對(duì)于某一實(shí)的有限維希爾伯特空間X上的子集C,C上的指示函數(shù)定義為:δC(x),即:δC(x)=0,當(dāng)x∈C；δC(x)=+],當(dāng)x/∈C.

3)函數(shù)f:Rn→R,那么函數(shù)f的共軛函數(shù)f?定義為:

4)對(duì)于給定的閉的真凸函數(shù)f:X→(?∞,+∞],與f相關(guān)的臨近點(diǎn)映射Proxf(.)定義為:

5)矩陣內(nèi)積:設(shè)A,B∈Rn×n,稱(vecA)T(vecB)為矩陣的內(nèi)積.其中Trace(A)為矩陣A的跡,簡(jiǎn)記為T(mén)r(A);vecA=(a11,a12,···,a1n,a21,a22,···,a21,···,an1,an2,···,ann)為矩陣A的向量化.

2.2ADMM

簡(jiǎn)單介紹一下ADMM算法框架,該方法用以求解帶有等式約束或小于等于型不等式約束,并且其中變量可分開(kāi)交替求解的模型.最早由Glowinski和Marrocco[18]以及Gabay和Mercier[19]提出,該方法普遍應(yīng)用于大規(guī)模問(wèn)題及機(jī)器學(xué)習(xí)等領(lǐng)域.此類問(wèn)題一般形式如下:

其中f:Xy(?],+]]和g:Xy(?],+]]是閉的真凸函數(shù),A:XyZ和B:XyZ是線性算子,X,Y,Z是實(shí)有限維歐幾里得空間,該空間上內(nèi)積定義為:h.,.i,其誘導(dǎo)范數(shù)為:||.||.此問(wèn)題增廣拉格朗日函數(shù):

求解(6)的ADMM具體算法框架如下:

§3 算法

3.1 求解問(wèn)題(1)的不精確dADMM

令p(X)=%||X||?,則可以將問(wèn)題(4)改寫(xiě)為:

現(xiàn)在給出求解問(wèn)題(9)的不精確dADMM算法.

3.2 子問(wèn)題

本小節(jié)給出不精確dADMM算法中求解子問(wèn)題的詳細(xì)步驟,即關(guān)于變量z和W的求解,具體過(guò)程如下:

問(wèn)題(14)有唯一解析解,可以通過(guò)對(duì)G作奇異值分解求解.假設(shè)G的奇異值分解為:

其中U∈Rp×s和V∈Rq×s都是具有正交列的矩陣,ξ∈Rs是分量為矩陣G的正奇異值組成的向量,按降序排列ξ1≥ξ2≥···≥ξs>0,s≤min{p,q}.對(duì)于給定的向量X∈Rs,令x+=max{x,0},其中最大值是按分量獲取的,即x每個(gè)分量與0的最大值.由[16],問(wèn)題(14)的解為:

因此根據(jù)G的奇異值分解,可以解得關(guān)于w的閉形式的解

3.3 不精確dADMM算法的收斂性

本節(jié)說(shuō)明求解對(duì)偶問(wèn)題的不精確dADMM算法的收斂性.參照文獻(xiàn)[20]和[21]的定理5.1建立該算法的全局收斂性,具體過(guò)程可參考文獻(xiàn)[21],此處只考慮其中S=0,T=0的情況:

式中：α和β分別為價(jià)值函數(shù)收益區(qū)域和損失區(qū)域的凹凸系數(shù)[24]，表示X方主體對(duì)待收益和損失的風(fēng)險(xiǎn)態(tài)度，α,β∈(0,1);λ為損失規(guī)避系數(shù)[25]，表示X方主體的損失規(guī)避程度，λ>1。

推論1假設(shè)對(duì)偶問(wèn)題(11)的解集非空,約束條件成立.若(zk+1,wk+1,Xk+1)是由不精確dADMM算法產(chǎn)生,其中,那么序列(zk+1,wk+1)收斂到對(duì)偶問(wèn)題(11)的最優(yōu)解,而Xk+1收斂到原問(wèn)題(4)的最優(yōu)解.

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

實(shí)驗(yàn)在64位Windowins 10操作系統(tǒng)的聯(lián)想筆記本電腦上實(shí)現(xiàn)的,電腦配置為:Intel(R)Core(TM)i7-7500U CPU@2.70GHz 2.90GHz,4G運(yùn)行內(nèi)存,運(yùn)行環(huán)境為MATLAB 2017b.

以下實(shí)驗(yàn)中,對(duì)于給定的p,q,m,映射A(X)=(hA1,Xi,hA2,Xi,···,hAm,Xi),A?(y)=,即矩陣A的每一列為Ai的向量化,定義A的矩陣形式

4.1 停機(jī)準(zhǔn)則

為了檢測(cè)逼近最優(yōu)解的程度,定義KKT(Karush?Kuhn?Tucker)殘差：

其中

對(duì)于給定的精度,算法如果滿足ηkkt<10?5或者迭代次數(shù)超過(guò)10000次,則停止迭代.

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

1)不同維度對(duì)比

本小節(jié)通過(guò)隨機(jī)數(shù)據(jù)對(duì)比不同維度的矩陣,迭代步數(shù),滿足停機(jī)準(zhǔn)則時(shí)的誤差及對(duì)應(yīng)時(shí)間的變化.對(duì)于給定的p,q,m,Ai和b都是隨機(jī)產(chǎn)生的稀疏數(shù)據(jù).計(jì)算單位為:秒(s)

表1 dADMM算法下不同維度數(shù)據(jù)數(shù)值結(jié)果

2)對(duì)比從原問(wèn)題和對(duì)偶問(wèn)題用不精確ADMM算法

通過(guò)引入變量Y,問(wèn)題(4)轉(zhuǎn)化為:

問(wèn)題(15)的增廣拉格朗日函數(shù)為:

現(xiàn)在給出求解問(wèn)題(15)的不精確ADMM算法.

通過(guò)將核范數(shù)最小二乘問(wèn)題原始模型形式轉(zhuǎn)化與對(duì)偶問(wèn)題做迭代次數(shù),停機(jī)準(zhǔn)則及計(jì)算時(shí)間上的對(duì)比.對(duì)于給定的p,q,m,Ai和b都是隨機(jī)產(chǎn)生,計(jì)算單位為:秒(s),具體比較結(jié)果如下:

表2 dADMM算法和pADMM算法對(duì)比

通過(guò)對(duì)比以上結(jié)果,得到從對(duì)偶解決該問(wèn)題明顯比從原始問(wèn)題做消耗時(shí)間更少,迭代次數(shù)也相對(duì)較少,成本更低.

另外對(duì)比對(duì)偶和原始不精確ADMM算法迭代計(jì)算中前后兩次解的相對(duì)誤差

此處令p=100,q=100,產(chǎn)生隨機(jī)數(shù)據(jù)做數(shù)值實(shí)驗(yàn),隨著迭代次數(shù)變化規(guī)律,誤差對(duì)比如下:

圖1 dADMM算法和pADMM算法前后兩次解誤差對(duì)比

隨著迭代次數(shù)增加相對(duì)于從原問(wèn)題出發(fā)的不精確ADMM,不精確的dADMM方法前后兩次求解所得最優(yōu)解的相對(duì)誤差明顯變化趨勢(shì)波動(dòng)較小且接近于0.因此足夠說(shuō)明我們從對(duì)偶問(wèn)題出發(fā)求解核范數(shù)最小二乘問(wèn)題的優(yōu)越性和穩(wěn)定性.

3)多變量線性回歸模型

本節(jié)將參照文獻(xiàn)[16]中的做法,對(duì)多變量線性回歸模型[22]通過(guò)形式轉(zhuǎn)換,求解如下拉格朗日松弛問(wèn)題.通過(guò)隨機(jī)產(chǎn)生數(shù)據(jù)來(lái)說(shuō)明不精確dADMM方法在多變量線性回歸問(wèn)題中應(yīng)用的優(yōu)越性.

其中A(X):=vec(ΛX),Λ∈Rm×m是一個(gè)正定對(duì)角矩陣,λ≥0.

其中w∈Rm×n.

如下對(duì)不精確的dADMM與文獻(xiàn)[16]中的APGL做KKT殘差和時(shí)間對(duì)比,其中對(duì)于給定的m,n及Λ=diag(rand(m,1)),M=randn(m,r)?randn(r,n),R=randn(m,n),b=vec(ΛM+0.01||ΛM||F/||R||FR),計(jì)算單位為:秒(s).通過(guò)以上對(duì)比可以得到,隨著維度增大不精確的dADMM算法迭代次數(shù)變化并不是多大,所用時(shí)間明顯增加.相比于APGL算法,不精確dADMM算法所需時(shí)間及迭代次數(shù)更少,更具有穩(wěn)定性.

表3 dADMM算法和APGL算法對(duì)比

此處令m=n=1000,按上述方法產(chǎn)生隨機(jī)數(shù)據(jù),分別從KKT殘差和每次迭代所需時(shí)間對(duì)比不精確dADMM算法和APGL算法,計(jì)算單位為:秒(s).

圖2 dADMM算法和APGL算法KKT殘差對(duì)比

從不精確的dADMM算法和APGL算法下的多變量線性回歸模型的對(duì)比,明顯不精確的dADMM算法KKT殘差收斂后相對(duì)更小,且收斂更快.

圖3 dADMM算法和APGL算法時(shí)間對(duì)比

對(duì)不精確的dADMM算法和APGL算法下的多變量線性回歸模型做每步時(shí)間上的對(duì)比,明顯不精確的dADMM算法每步迭代時(shí)間相對(duì)更少,更具高效性.

§5 總結(jié)

通過(guò)不精確的ADMM算法求解核范數(shù)正則最小二乘問(wèn)題的對(duì)偶模型進(jìn)而解得原問(wèn)題,同時(shí)在一定假設(shè)條件下說(shuō)明該優(yōu)化算法的全局收斂性.通過(guò)相應(yīng)的實(shí)驗(yàn),說(shuō)明了本文算法的高效性和穩(wěn)定性,可以在更少的迭代次數(shù)內(nèi)求得該問(wèn)題.