大規模非線性最佳化問題的並行算法及套用研究

《大規模非線性最佳化問題的並行算法及套用研究》是依託山東科技大學，由賀國平擔任項目負責人的面上項目。

基本介紹

• 中文名：大規模非線性最佳化問題的並行算法及套用研究
• 項目類別：面上項目
• 項目負責人：賀國平
• 依託單位：山東科技大學

項目摘要

目前，大部分最佳化算法，包括人們熟知的序列二次規划算法和序列線性方程組算法等，在解決如支持向量機等大規模或超大規模最佳化問題時，都因計算時間過長、計算誤差積累，難以達到實際套用的目的，解決該困難的一個方向，是研究適合高速並行計算機或機群系統的最佳化算法。本課題主要研究大規模最佳化問題的並行算法及其在支持向量機等模型求解中的套用。首先研究無約束問題的高效並行變數分布和並行變數轉換等新算法，分析其全局收斂性質及並行效率；其次研究特殊約束問題的並行序列二次規劃和序列線性方程組算法，試圖獲得全局並行、子問題高效求解的算法；第三個內容是利用約束剖分技術，研究帶一般約束的非線性最佳化問題的並行算法；第四個內容是將相應的並行最佳化新算法進行特殊化，套用於支持向量機等超大規模問題的求解；最後，將建立大規模最佳化問題和並行最佳化問題的數值測試平台，進行大量數值實驗，驗證並改進所提出的各種新算法的有效性。

結題摘要

本項目的主要研究內容是求解大規模最佳化問題的並行算法及其在支持向量機等模型求解中的套用。首先研究了無約束問題的高效並行變數分布和並行約束轉換等新算法，使每步下降量加大，並證明了算法具有全局收斂性且收斂比與處理器個數無關；其次，對於特殊約束問題，提出了高效並行的序列二次規劃（SQP）和序列線性方程組（SSLE）算法，在子問題的構造方面，充分考慮同步或異步、局部下降和全局收斂的關係，使算法子問題求解的工作量減少，整體快速收斂。最後，對一般約束的非線性最佳化問題，將約束剖分概念引入並行最佳化算法的設計，提出了一般約束情況下新的並行算法，並用SSLE等方法解決子問題求解，在適當條件下證明了算法的收斂性。同時，以一般約束最佳化問題並行算法的研究工作為基礎，本課題組成員對超大規模支持向量機問題的求解進行了深入研究，利用支持向量機模型的特殊結構，通過對支持向量機進行算法層次的並行化處理，獲得了較為有效的並行算法，使得支持向量機的求解既能快速進行，又有理論保障。對支持向量機模型的分解算法及分散式算法進行了研究，並對基於支持向量機模型的界約束最佳化問題的求解算法進行研究，得到若干成果。此外，本課題組還對隱私保護支持向量機問題及支持向量機的套用作了較多研究工作；開展了網路機群環境下並行算法的實現研究，初步構建了並行最佳化方法的數值測試平台。對二階錐最佳化及互補問題的求解方法進行研究，獲得了一系列具有全局收斂性和局部超線性收斂速度的有效算法，並通過數值試驗驗證了算法的有效性。