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

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