史冰冰, 王青松

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

§1 背景簡介

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

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

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

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

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

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

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

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

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

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

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

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

§2 預(yù)備知識

2.1 基本概念及符號說明

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

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

2)對于某一實的有限維希爾伯特空間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)對于給定的閉的真凸函數(shù)f:X→(?∞,+∞],與f相關(guān)的臨近點映射Proxf(.)定義為:

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

2.2ADMM

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

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

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

§3 算法

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

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

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

3.2 子問題

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

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

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

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

3.3 不精確dADMM算法的收斂性

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

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

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

§4 數(shù)值實驗

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

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

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

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

其中

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

4.2 實驗

1)不同維度對比

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

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

2)對比從原問題和對偶問題用不精確ADMM算法

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

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

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

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

表2 dADMM算法和pADMM算法對比

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

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

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

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

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

3)多變量線性回歸模型

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

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

其中w∈Rm×n.

如下對不精確的dADMM與文獻(xiàn)[16]中的APGL做KKT殘差和時間對比,其中對于給定的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),計算單位為:秒(s).通過以上對比可以得到,隨著維度增大不精確的dADMM算法迭代次數(shù)變化并不是多大,所用時間明顯增加.相比于APGL算法,不精確dADMM算法所需時間及迭代次數(shù)更少,更具有穩(wěn)定性.

表3 dADMM算法和APGL算法對比

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

圖2 dADMM算法和APGL算法KKT殘差對比

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

圖3 dADMM算法和APGL算法時間對比

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

§5 總結(jié)

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