一種求解dacig-sshr模型的快速分解算法

一種求解dacig-sshr模型的快速分解算法

0總結(jié)線性回歸是一種非常經(jīng)典的數(shù)學模型，在數(shù)據(jù)處理、機器學習和統(tǒng)計學習中得到了廣泛應(yīng)用。這是因為壓縮感知理論。1基于乘子交替方向法的求解經(jīng)典的線性回歸問題可刻畫為:式中,β∈R式中,‖·‖上述模型是標準的帶線性約束的凸優(yōu)化模型,而增廣拉格朗日函數(shù)是求解此類問題的經(jīng)典方法之一.但是,直接使用增廣拉格朗日方法會使得子問題變量耦合在一起,不利于算法的實現(xiàn).因此,根據(jù)目標函數(shù)的可分離性,文獻[6]利用乘子交替方向法進行求解,且取得了良好的數(shù)值效果.美中不足之處是,直接利用乘子交替方向法求解,其關(guān)于β部分的子問題沒有顯式表達式,這給算法的實現(xiàn)增加了一定難度.隨后,文獻[7]巧妙地將與β有關(guān)的子問題進行線性化,提高了乘子交替方向法的可操作性,也在一定程度上減少了算法的計算時間.但他們的方法要求估計一個矩陣的譜半徑,這也并非一件易事.基于上述原因,本文尋求一種新的簡單易行的算法.2變量分離算法針對模型(3),引入增廣拉格朗日函數(shù):式中,γ>0是罰參數(shù),λ表示拉格朗日乘子.給定(β顯然,乘子交替方向法主要的任務(wù)就是求解子問題(5)和問題(6).由于子問題(5)可以顯式求解,子問題(6)的求解直接決定了算法的有效性.但由于X為了簡化數(shù)學符號,記A∶=X式中,ρ>0是一個懲罰因子.針對模型(8),相應(yīng)的增廣拉格朗日函數(shù)為:式中,λ和γ分別代表拉格朗日乘子和罰參數(shù).根據(jù)乘子交替方向法的Gauss-Seidel迭代思想,給定(x類似迭代格式(5)~(7),上述方法的主要工作量集中在子問題(10)~(12).下文中,本文主要討論式(10)~(12)的具體表達式.首先,關(guān)于變量z的子問題(10)歸結(jié)為:式中,diag(D)表示由D矩陣對角元素構(gòu)成的列向量.最后,將(z由上述分析可見,本文新提出的算法其每個子問題都能顯式求解,這相比文獻[5]中的乘子交替方向法更容易實現(xiàn).當矩陣A具有某些特殊結(jié)構(gòu)時,可以借助一些快速矩陣求逆方法對式(18)進行求解(例如:快速傅立葉變換).當矩陣A規(guī)模較大且無特殊結(jié)構(gòu)時,(γA當處理(18)的病態(tài)情形時,在共軛梯度法中引入預(yù)處理迭代技術(shù)增加算法的穩(wěn)定性和可靠性,這也是新算法的一個潛在優(yōu)勢.綜上分析,本文的分解算法過程可描述如下:1)輸入初始迭代點(x2)通過式(15)更新z4)通過式(18)或(19)更新β3計算公式的數(shù)值測試本節(jié)對新提出的算法進行數(shù)值模擬來檢驗算法的優(yōu)劣.考慮到β子問題的計算方式,新算法分為式(18)的精確計算(簡記為“New-accurate”)和式(19)的一步迭代近似計算(簡記為“New-one”).同時,將新算法與文獻[5]中的乘子交替方向法(簡記為“ADMM”)進行比較.所有算法都用MATLAB進行編程實現(xiàn),其中文獻[5]的ADMM算法程序由該文作者提供.類似文獻[4]的測試情況,本節(jié)仍考慮兩種類型的系數(shù)矩陣X:單位列向量系數(shù)矩陣和行正交系數(shù)矩陣.實驗中設(shè)定初始值迭代點為(x3種算法的數(shù)值結(jié)果如表1和表2所示,其中包括計算迭代次數(shù)(Iter.)、以秒為單位的CPU運行時間(Time)和近似解的誤差(ρ表1和表2的數(shù)值結(jié)果表明New-one算法和ADMM在得到質(zhì)量相當?shù)慕平鈺r,New-one所需的CPU運行時間比后者要少,這進一步從數(shù)值上驗證了本文新方法在求解子問題方面的優(yōu)勢.若直接使用式(18)更新β因表1、表2中的數(shù)據(jù)只是顯示了計算結(jié)果的平均值,為了更加清晰展現(xiàn)每組隨機數(shù)據(jù)的計算結(jié)果,當X分別為行正交矩陣和單位列向量矩陣時,3種算法求解第i個問題時最大、最小和平均的(內(nèi))迭代次數(shù),如圖1和圖2所示;與之相對應(yīng)的,誤差量ρ圖5和圖6分別畫出了當(n,p,s)=(72,256,8)時兩種不同類型系數(shù)矩陣對應(yīng)的數(shù)值解情況.兩幅圖可看出New-one恢復出來的數(shù)值解令人滿意.4基于快速分解的質(zhì)量評分解鑒于直接使用乘子交替方向法求解Dantzig-Selector模型時子問題不具有顯式迭代格式的缺陷,本文引入一種新的模型刻畫技巧,提出了一種子問題簡單易行的分解算法.通過測試兩種不同類型的隨機數(shù)據(jù),初步的數(shù)值結(jié)果表明新算法在CPU運行時間方面有較明顯的優(yōu)勢.新的快速分解算法解Dantzig-Selector模型的算法步驟如下:3)通過式(16)更新x5)通過式(13)更新λ式中,其次,將z根據(jù)式(17)的一階最優(yōu)性條件立得式中,另外,根據(jù)文獻[4]的測試方法,對兩種不同類型的系數(shù)矩陣情況分別測試5組規(guī)模不同的隨機數(shù)據(jù),相關(guān)維數(shù)設(shè)定為(n,p,s)=(72i,256i,8i