1：解決的問題模型如下：

?
或者約束條件可以適當的松弛，即為如下模型：?
?
當然約束條件取范數，數據獲取的比較準確，結果逼近的效果更好，防止過擬合。如果取?范數，則是獲取的數據，受到污染比較嚴重。并且?本身就是稀疏的。這也是人的經驗對于模型的成功也是很重要的。?
2：幾類優化算法?
(1)梯度投影算法Gradient Projection Methods?
原問題可以變為如下問題：?
?
下面介紹兩種方法對其進行處理。?
i)上式又等價于：?

?
所以就有如下記號和約定：?
?
更新?時沿著負梯度的方向下降最快。但是只是局部最小值。?
?
其中?是步長，可以用線搜索的方法來確定最優步長。?
下介紹第二種方法 truncated Newton interior-point method.?
ii)上式又等價于：?
?
利用內點法的把約束條件給罰到目標函數上去。?
在這里我們對約束條件利用logarithmic barrier函數進行改寫。?
?
在這里，我們可以看到當?越接近的時候，函數值會變得越大。當?無限趨近于時，則函數值無限趨于無窮大。所以只有當?趨近于0時候，函數值才趨近于一個常數。?
所以上式可以等價于如下模型：?

然后利用牛頓算法進行求解計算。

(2)迭代閾值收縮算法 Iterative Shrinkage-Thresholding Methods?
對于一般的模型：?
?
其中：

對?二次近似。則問題轉變成如下：?
?
可以適用迭代閾值算法。關于l_{1}范數最優化的迭代閾值算法的證明可以參見我的另一篇博客

(3)近端梯度算法 Proximal gradient method?
其處理的模型如下：?
?
其中是連續可微的，微分函數滿足利普希茨條件成立：?
?
其中相當于代替的二階偏導。?
那么可以進行如下算法來解決問題：?
?
說明：?
第一步的更新：按照沿著負梯度的方向下降最快?
第二步的更新：有數值解，進行軟閾值操作。?
(4)交替方向法 Alternating Direction Methods?
其實利用的是拉格朗日算法，來進行更新出來。解決的模型如下：?
?
其拉格朗日函數如下：?
?
問題變為分別最小化。?
說明：?
更新時，固定，直接求導，有數值解。?
更新?時，固定經過化簡，可以運用軟閾值進行操作計算。?
更新時，固定，直接求導，有數值解。

總結

以上是生活随笔為你收集整理的l1范数最小化快速算法【文献阅读】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。