《兩類大規模矩陣最佳化問題的算法研究與軟體設計》是依託瀋陽航空航天大學，由劉勇進擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：兩類大規模矩陣最佳化問題的算法研究與軟體設計
- 項目類別：青年科學基金項目
- 項目負責人：劉勇進
- 依託單位：瀋陽航空航天大學
項目摘要,結題摘要,
項目摘要
凸半定規劃和核範數矩陣最佳化問題是兩類重要的矩陣最佳化問題，在結構最佳化，最優控制，組合最佳化，套用統計，金融管理等領域，許多問題的模型都是半定規劃或核範數矩陣最佳化模型。實際中有重大價值的兩類問題往往是大規模的，因此系統研究這兩類大規模凸矩陣最佳化問題的算法理論和軟體設計有著重大的意義。本項目以凸規劃的基礎理論和算法為基礎，研究大規模凸半定規劃問題的迫近點-加速迫近梯度方法和加速迫近梯度-(半) 光滑Newton方法，大規模核範數最佳化問題的迫近點-加速迫近梯度方法，迫近點-(半) 光滑Newton方法和加速迫近梯度-(半) 光滑Newton方法，並研製上述算法的matlab軟體。算法的理論分析以半光滑理論以及相關的變分分析為基礎，算法的數值實現充分利用矩陣的特徵值和奇異值理論。本項目旨在獲得兩類大規模問題的有效算法及數值軟體，推動大規模矩陣最佳化特別是非對稱矩陣最佳化理論和算法的進一步研究。
結題摘要
非對稱矩陣最佳化問題是一類重要的矩陣最佳化問題，在結構最佳化，最優控制，數值代數，套用統計，壓縮感知等領域，許多問題的模型都是非對稱矩陣最佳化的模型。本項目以凸規劃的基礎理論和算法為基礎，研究了大規模凸非對稱矩陣最佳化的有效算法，並研製了相應的Matlab程式，其代表性結果可歸納如下： 1. 針對大規模矩陣核範數最佳化問題，研究了求解該問題的可實現的迫(鄰)近點算法框架，該算法框架包含了原始、對偶以及原始-對偶三種不同形式的迫近點算法。基於算法編制的軟體包PPApack能夠處理矩陣規模達到10萬維的大規模(低秩)矩陣核範數最佳化問題。這一結果發表在國際頂級最佳化期刊Mathematical Programming, Series A，受到國際國內同行廣泛關注，論文已被他引62次。 2. 針對帶線性等式和線性不等式約束的矩陣譜範數逼近問題(核範數最佳化問題的對偶問題)，提出了非精確半光滑牛頓-共軛梯度對偶迫近點方法。研究了矩陣核範數單位球投影運算元B-微分的具體計算公式，並證明了：當對偶鄰近點算法子問題的原約束非退化條件成立時，用於求解子問題的半光滑牛頓方法至少具有局部超線性收斂率。通過Matlab語言有效實現，對於超過500維的大規模問題，我們的算法是第一個具有高精度、穩定、高效特性的算法。 3. 基於參數方法，研究了求解一閉半空間與可變盒子交投影運算元顯示解的強多項式算法，並分析了算法至多進行O(mlog(m))步可得到投影運算元的顯示解，其中m為向量的維數。通過對算法的Matlab有效實現，得到了相應的數值結果，數值結果表明，對於向量規模達到100萬維的問題，只需要大約18秒就能得到其投影運算元的顯示表達式。項目研究成果以論文的形式提供，共完成10餘篇論文，其中8篇正式發表。本項目取得的大規模矩陣最佳化問題的有效算法及數值軟體的成果，可推動大規模矩陣最佳化在相關領域的套用。
