大規模凸最佳化問題的一階分裂算法研究

《大規模凸最佳化問題的一階分裂算法研究》是依託南京大學，由何炳生擔任項目負責人的面上項目。

基本介紹

• 中文名：大規模凸最佳化問題的一階分裂算法研究
• 項目類別：面上項目
• 項目負責人：何炳生
• 依託單位：南京大學

項目摘要

信息科學和工程領域中的許多大規模最佳化問題，如視頻處理、機器學習中的問題, 可以歸結為一類具有等式約束的可分凸最佳化問題。在一些最新的套用領域，以交替方向法為代表的處理兩個可分運算元凸最佳化問題的分裂算法，其有效性已得到充分證實。一階分裂算法是求解大規模凸最佳化的有效算法已成共識。本項目對一階分裂算法中幾個癥結問題：原始-對偶混合梯度法及交替方向法對多個運算元問題直接推廣的收斂性質、影響收斂速度的參數自調比準則進行深入研究。此外，在收縮意義下建立分裂算法的統一框架，並對收斂複雜性和加速策略進行系統的研究。採用鬆弛、分裂與整合等技術，為求解線性約束的大規模可分凸最佳化問題提供理論上有複雜性保證，實際計算中又行之有效的分裂方法。

結題摘要

本項目致力於全面系統地研究大規模凸最佳化問題的一階分裂算法的理論、算法設計以及套用。主要結果如下：證明了交替方向法在非遍歷意義下的計算複雜性；提出了用於刻畫一階算法的預測-校正框架，簡化了一階分裂算法的收斂性證明與收斂速率分析；證明了對具有多塊分離結構的凸最佳化問題，用直接推廣的交替方向法計算不一定收斂，進而提出了一系列高效、穩健並具全局收斂性的預測-校正收縮型算法。這些原創性成果實質性地加深了對以交替方向法為代表的一階分裂算法的系統理解，極大地拓展了這類算法的適用範圍，得到了國內外學者的廣泛關注及認可。