[發明專利]一種基于ADMM算法的數據處理方法

有效

• 申請號: 201610052280.X
• 申請日: 2016-01-26
• 公開（公告）號: CN105740208B
• 公開（公告）日: 2019-05-14
• 發明（設計）人: 沈輝;袁曉彤
• 申請（專利權）人: 南京信息工程大學
• 主分類號: G06F17/16
• 分類號: G06F17/16
• 代理公司: 南京縱橫知識產權代理有限公司 32224
• 代理人: 董建林

本發明公開了一種基于ADMM算法的二次函數分布式實現方法，步驟包括：啟動系統，讀入二次目標函數的系數矩陣A和b，將數據分為N個處理塊，采用二次函數分布式更新的表達式進行其中每一個處理塊的計算，各處理塊計算完成后，將各處理塊結果匯總，完成計算過程。本發明所提供的一種基于ADMM算法的二次函數分布式實現方法，利用了二次函數表達式和LASSO表達式之間的關系，在LASSO分布式更新的基礎上推導出了二次函數的分布式更新表達式，實現了在大數據背景下，目標函數是二次函數的分布式計算，大大提高了計算速度。

技術領域

發明涉及一種基于ADMM算法的二次函數分布式實現方法，屬于信息處理技術領域。

背景技術

目前，我們已然生活在一個大數據的時代，各行各業的數據正在迅速膨脹增長，毫無疑問，如何高效合理的處理這些數據，將成為企業提高核心競爭力的關鍵因素。從數學角度看，大數據意味著樣本量的增加以及維度的增加，在不考慮真實環境下所消耗的計算時間，數學家們已經提出了很多好的迭代算法，但是面對真實的Gb甚至是Tb以上的數據時，一般的硬件都無法滿足直接運行這些算法的要求，在目前條件下，并行化、分布式計算是一種比較好的解決思路。將一個大規模問題分散到多個機器、多個核上，這些好的算法便可以大規模運用，而ADMM算法正是在解決大規模問題上起到了顯而易見的效果。

ADMM算法整合了許多經典算法的優化思路，提出了一個比較好實施的分布式計算框架，簡單來講，ADMM算法充分利用了目標函數的可分離性，它將原來的問題轉變成了更容易求解的若干子問題，盡管看上去未知量似乎變多了，但是實際上每一個子問題的求解都得到了大大的簡化，通過交替求解子問題，最終實現原始問題的求解。針對眾多不同的數學模型，研究者們已經給出了它們的分布式算法，其中就包括了LASSO(least absoluteshrinkage and selection operator)問題。然而當LASSO表達式展開之后轉變成了一個二次函數問題時：盡管表達式上相近，但是LASSO的分布式更新算法已經不再適用。

二次函數模型是一個常見的數學模型，在信號處理、統計學、生物系統、人工智能等領域都有著廣泛的應用。并且在統計優化領域中，很多函數模型采用梯度法來求解目標函數，而其最終的本質就是轉化成對一個二次函數模型的優化，所以將二次函數模型用分布式的方式來計算實現是非常有意義的。

發明內容

本發明所要解決的技術問題是提供一種基于ADMM算法的二次函數分布式實現方法，能夠實現目標函數是二次函數的分布式計算。

為解決以上技術問題，本發明采用的技術方案是：一種基于ADMM算法的二次函數分布式實現方法，步驟包括：啟動系統，讀入二次目標函數的系數矩陣A和b，將數據分為N個處理塊，其中任一個處理塊的二次函數分布式更新的表達式為：

式中，A_ii可以看成是已知的矩陣A中沿著對角線上取的一個方陣，為A對應的行乘上x再除以塊數，b_i為b中第i個處理塊對應的部分，為中間變量；λ為拉格朗日乘子，ρ>0為懲罰函數，i為第i個處理塊，T為矩陣轉置，k為第k次迭代，x為待求解的目標變量，x_i為第i個處理塊中的目標變量；

各處理塊計算完成后，將各處理塊結果匯總，完成計算過程。

所述二次函數分布式更新的推導過程為：

將LASSO問題表示為：

其中，B、D為中間過渡變量，

目標函數為由LASSO展開后的二次函數：

結合(4)、(5)兩式：