《求解可分凸規劃的並行分裂算法研究》是依託南京大學，由陶敏擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：求解可分凸規劃的並行分裂算法研究
- 項目類別：青年科學基金項目
- 項目負責人：陶敏
- 依託單位：南京大學
項目摘要,結題摘要,
項目摘要
大量實際問題，如壓縮感知，數據挖掘中的主成份分析，分散式網路問題，最終都歸結為一類具有等式約束的可分凸規劃問題。由於目標函式含有多個運算元（指多於兩個），這給經典的分裂算法的直接套用帶來困難。又因為這些問題來源實際，問題的規模龐大，數據集結構複雜，因而設計行之有效的一階算法已經迫在眉睫。我們將利用算法分裂的思想和鬆弛的技巧，在充分考慮這類問題的特殊結構的基礎上，設計適合大規模問題的一階算法。通過降維和鬆弛的思想，並行計算等手段，將此類可分凸規劃問題轉化為一系列易於求解的低維子問題。當這些低維子問題不具有顯式解時，我們採用適度鬆弛的方法，非精確求解它，使得鬆弛後的子問題具有顯式解。同時，我們也會根據各類實際問題的需要，設計適用於問題需要的並行分裂算法。最後，我們從理論上分析算法的全局收斂性和收斂速率，進一步考慮加速策略。從而解決了求解大規模凸規劃問題尚無成熟有效的並行算法的難題。
結題摘要
大量實際問題，如壓縮感知，數據挖掘中的主成分分析，分散式網路問題，最終都轉化成可分凸規劃問題。通常，這些起源於實際套用問題的可分凸規劃問題都具有規模大，結構特殊等特點， 所以採用分裂型算法來求解是很自然的想法。這裡分裂的思想是指分解和降維。採用該方法的益處是使得分解和降維以後的子問題更容易求解。對於分裂以後得到的子問題通常按照執行的順序，大致可以將分裂型算法分成交替型算法，並行算法和部分交替，部分並行的算法。對於交替型算法，最有效的當屬交替方向法。然而，採用直接推廣的交替方向法求解可分凸規劃問題，當可分運算元等於三塊時，該方法被證明有可能是發散的。對於並行算法，它有著很強的套用背景，例如，傳統中央式網路具有信息傳輸成本高，網路架構缺乏穩健性等遺憾，所以，分散式網路應運而生。然而，分散式網路問題的求解需要採用並行分裂算法，原因是每個節點只可以利用和它相鄰節點的信息。 本項目著眼於可分凸規劃的分裂算法設計和分析，並取得了如下的進展： 1. 針對各類套用問題設計了四類多元分裂並行算法,根據所求解模型目標函式的可分凸運算元的特性，分別設計了不同的求解子類問題的策略。並將其套用到分散式網路問題的求解當中。2. 分析了提出的四類並行算法的全局收斂性和計算複雜度。3.對於某一類可分凸規劃問題，研究了不精確加速分裂算法，該算法對於目標函式可分的情形，可以並行執行各個子問題的求解。而且，該算法採用了比較鬆弛的不精確準則，可以自適應的選定合適的步長，這對於現存的一些分裂算法，比如交替方向法需要經驗選取步長相比，無疑是一個更貼合實際的進步。4.分析了預條件交替方向法求解二次規劃問題的漸進斂散性；並結合了SOR鬆弛的思想。 Glowinski 於1984年在他的專著Numerical Methods for Nonlinear Variational Problems中提出對於帶鬆弛因子的交替方向法，是否可以將鬆弛因子的範圍從(0,\frac{1+\sqrt{5}}{2})擴展到區間(0,2)，卻仍然具有全局收斂性的公開問題。我們證明了當交替方向法求解線性約束的二次規劃問題時，該鬆弛因子的範圍可以取(0,2)，並且仍然具有全局收斂性。並且分析了其線性收斂性。所以，我們部分回答了Glowinski提出的公開問題。
