求解LASSO 問題的廣義對稱交替方向乘子算法

蔣 峰， 黨亞崢， 何澤秀

（上海理工大學(xué) 管理學(xué)院， 上海200093）

0 引 言

隨著大數(shù)據(jù)時代的到來，數(shù)據(jù)收集技術(shù)有了巨大的發(fā)展，如何有效地從大規(guī)模數(shù)據(jù)中挖掘出潛在的有用信息成為了新的研究熱點。 線性模型是當前比較常用的數(shù)據(jù)挖掘手段，其理論豐富，應(yīng)用廣泛，在農(nóng)業(yè)、工程技術(shù)、經(jīng)濟、管理、工業(yè)、生物等領(lǐng)域取得了長足的發(fā)展［1］。 線性模型應(yīng)用的范圍越廣，模型的準確性就顯得越重要。 就線性模型而言，其準確性主要取決于變量的選擇和回歸系數(shù)的取值。 受Ridge Regression 和Nonnegative Garrote 算法的啟發(fā)，Tibshirani 提出了一種新的變量選擇方法，即最小絕對收縮和選擇算子（Least absolute shrinkage and selection operator， LASSO）［2］。 LASSO 問題包含平方誤差的求和和正則化項。 L1 正則化項能夠避免模型過擬合問題，使得模型更加穩(wěn)定［3］。

解決LASSO 問題的方法很多，Efron 提出了最小角回歸算法求解Lasso 問題。 該算法通過消除回歸系數(shù)的異號情況得到LASSO 問題的解［2］。 陳善雄等人考慮各個變量在模型中所占比重不同，提出了多維權(quán)重求解算法［3］。 該算法在最小回歸算法的基礎(chǔ)上加入主成分分析、獨立權(quán)數(shù)法、基于Intercriteria 相關(guān)性指標的重要性評價法這3 種權(quán)重評價方法，優(yōu)化變量的選擇。 數(shù)值實驗表明該方法進一步提升了求解LASSO 問題的準確性。 在解決大規(guī)模數(shù)據(jù)問題中，交替方向乘子法（ADMM）得到廣泛應(yīng)用。 ADMM 算法將原始的凸優(yōu)化問題分解為多個子問題進行分別求解，最后再計算拉格朗日乘子［4］。 這種方法在很大程度上減少了計算成本，提升了求解LASSO 問題的效率。

雖然ADMM 算法求解大數(shù)據(jù)背景下的LASSO問題速度較快，但是在很多實際應(yīng)用中， 精確地求解子問題難以實現(xiàn)， 或者需要很大代價。 因此本文提出了一種廣義對稱ADMM 算法。 該算法的主要創(chuàng)新之處是在對稱交替方向乘子法的x 極小化子問題中加入半近鄰項近似求解此問題。 此外，為進一步提高算法的收斂速度，引入了松弛算子。 通過具體的數(shù)值實驗表明，廣義對稱交替方向乘子法收斂速度比對稱交替方向乘子法更快。

1 LASSO 問題及廣義對稱ADMM 算法

1.1 LASSO 問題描述

機器學(xué)習(xí)中的凸優(yōu)化問題一般可以表示為

其中，x ∈Rn，P ∈Rm×n，u 是正則化參數(shù)。

1.2 廣義對稱ADMM 算法

ADMM 算法由Glowinski 等人提出［5］，主要用于求解形如式（3）的凸優(yōu)化問題

其中，A ∈Rm×n，X ?Rn、Z ?Rm是給定閉凸集；f：Rn→R ∪ {＋∞} 和g：Rm→R ∪ {＋∞} 為凸函數(shù)。

本文A 為單位矩陣，其迭代格式如下：

其中，y 為拉格朗日乘子，γ 是懲罰參數(shù)。 由式（3）可以看出，ADMM 算法先求解x 最小化問題，再求解z 最小化問題，最后再更新拉格朗日乘子y。

在文獻［6］中，對稱ADMM 算法被用于求解LASSO 問題。 然而，在大數(shù)據(jù)背景下，精確地求解（3）中的x 子問題難以實現(xiàn)，或者需要很大代價。 因此本文提出了一種廣義對稱ADMM 算法。

其中， α ∈（0，2］ 是松弛算子。 當α ＝1 時，（1.5）變?yōu)閷ΨQADMM 算法。

2 數(shù)值實驗

本節(jié)將廣義對稱ADMM 算法應(yīng)用于LASSO 問題。 在進行數(shù)值實驗時，選取矩陣P 并且規(guī)范化P中所有列。 取a 和σ 為隨機向量，b ＝Pa ＋σ，正則化參數(shù)取m ＝2 500，α ＝0.8，懲罰參數(shù)γ ＝1，矩陣此外，向量x， y， z 的初始值皆為零向量。

其中，δ ＝10－4。

表1 為應(yīng)用對稱ADMM 算法和廣義對稱ADMM 算法解決該問題的結(jié)果，其中Iter 表示迭代次數(shù)，CPU（s） 表示CPU 時間（以秒為單位）， n 表示矩陣P 的維數(shù)。 從表1 可以看出，本文提出的算法快于對稱ADMM 算法。

表1 LASSO 問題數(shù)值結(jié)果Tab.1 Numerical results for LASSO

為了進一步觀察2 種算法的收斂性，比較初始殘差和對偶殘差隨迭代次數(shù)的變化情況（縱軸分別是初始殘差和對偶殘差，橫軸是迭代次數(shù)）。 從圖1、圖2 中可以直觀地發(fā)現(xiàn)，盡管在算法迭代的某些階段，對稱ADMM 算法的初始殘差、對偶殘差減小更快，但是本文提出的算法先于對稱ADMM 算法收斂，因此廣義對稱ADMM 算法更高效。

圖1 對偶殘差的變化情況Fig.1 Evolution of primal residual

圖2 初始殘差的變化情況Fig.2 Evolution of dual residual

3 結(jié)束語

本文提出了一種求解LASSO 問題的廣義對稱ADMM 算法。 該方法的基本思想是在x 子問題中加入一個二次項，并且引入了松弛算子，從而提升算法效率。 數(shù)值實驗表明，本文提出的算法在求解高維的LASSO 問題時，相對于對稱ADMM 算法具有明顯的優(yōu)勢。 但是，如何選擇最優(yōu)的α 還需要進一步研究。