問題驅動的大型最佳化問題的可計算建模與算法探索

《問題驅動的大型最佳化問題的可計算建模與算法探索》是依託南京大學，由何炳生擔任項目負責人的重大研究計畫。

基本介紹

• 中文名：問題驅動的大型最佳化問題的可計算建模與算法探索
• 項目類別：重大研究計畫
• 項目負責人：何炳生
• 依託單位：南京大學

項目摘要

從不完全或者受污染的信息恢復全部正確信息在包括壓縮感知、圖像與信號處理、生物基因分析、以及機器學習等諸多領域有著廣泛套用。這類套用基礎課題受到包括菲爾茲獎獲得者在內的一大批數學家的重視。通過建立適當的數學模型，此類問題一般轉化為大規模結構型凸最佳化問題。在算法方面，PPA算法是求解凸最佳化問題最經典的方法之一，它通過求解系列子問題求得原問題的解。由於子問題往往仍然需要疊代求解，因此直接套用PPA一般相當複雜，在很多情況下甚至難以實現。本項目旨在利用問題的分離結構，通過對變數的合理鬆弛，設計易於實現的求解大規模結構型凸最佳化問題的鬆弛PPA算法；以及融合凸最佳化的鬆弛PPA算法和序列凸近似的思想，構建求解大規模結構型凸最佳化問題的序列PPA算法；並在理論分析與計算實踐相結合的基礎上編寫可以為實際套用服務的、高效的軟體程式；以及建立一些如何利用問題結構設計算法的具有普適意義的原理。

結題摘要

結構型最佳化問題大量出現在數據科學中。大規模最佳化問題宜採用一階方法求解已漸成共識。凸最佳化的一階最優性條件是一個混合單調變分不等式。在變分不等式的觀點下考慮問題, 求解結構型最佳化問題的一階方法與求解變分不等式的投影收縮算法有許多共同之處。基於項目組多年求解變分不等式方法的基礎，對求解數據科學中的問題，做了以下工作： 1. 提出了一類收斂性證明非常簡單的 PPA意義下的收縮算法，為圖像數據科學採用，受到著名圖像科學工作者的肯定；2. 對交替方向法這類被高度重視的有效方法，在遍歷意義和非遍歷意義下證明證明了它的 O(1/t) 的計算複雜性，提出了更合理和效率更高的對等校正乘子的乘子交替方向法；3. 對多個可分離運算元的問題，首先提出了有理論保證的預測－校正分裂算法，被包括美國 UCLA 的課題組在求解降維問題時採用；4. 提出了求解線性約束凸最佳化問題基於變分不等式的預測-校正方法的統一框架，既為這類方法的收斂性證明提供了簡便的證明，也為因問題所需構造方法、評判算法效率、提供了有效途徑。上述研究結果，均有論文在SIAM 系列刊物發表，並受到國際著名學者的長篇實質引用。