幾類矩陣最佳化問題的算法設計及其理論和套用

《幾類矩陣最佳化問題的算法設計及其理論和套用》是依託中國科學院數學與系統科學研究院，由劉歆擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：幾類矩陣最佳化問題的算法設計及其理論和套用
• 項目類別：青年科學基金項目
• 項目負責人：劉歆
• 依託單位：中國科學院數學與系統科學研究院

項目摘要

矩陣奇異值分解、非線性特徵值計算、主成分分析、張量分析、0-1整數規劃等重要的數學模型被廣泛套用於機器學習、材料科學、醫學統計、影像壓縮、管網設計等工程領域，而這些數學模型都可化為滿足一些特殊流形約束的矩陣最佳化問題。由於矩陣的流形約束通常結構複雜並且是非凸的，一般來說，求解這類問題的全局極小是NP難的；而當目標函式帶有非光滑項，或者問題同時帶有其它形式的約束時，求解問題的局部極小也變得非常困難。基於此，本項目主要研究幾類具有代表性的矩陣最佳化問題，並將分別針對這些問題的特性設計若干高效、穩定的算法。本項目還將對部分模型的最優性條件以及所設計的算法的收斂性進行理論分析，以期達到理論創新和方法創新的統一。本項目不僅可以促進我國最最佳化及相關交叉學科研究的發展；所提出的新方法還能被廣泛地套用到我國十二五規劃所涉及到的一些重點發展領域，為我國全面建設小康社會的發展目標作出新貢獻。

結題摘要

隨著科學技術的不斷進步和最最佳化研究的不斷發展，經典的以歐式空間中向量為變數的最佳化模型已經不能滿足各套用學科深入發展的需求，而以矩陣為變數的最佳化模型（矩陣最佳化模型），因其能夠刻畫更多的經典最佳化模型無法描述的套用問題，開始發揮越來越關鍵的作用，並成為最最佳化研究的一類新熱點。最近二十年里，大量關於矩陣最佳化模型的理論和算法研究的湧現更是推動了矩陣最佳化成為被套用學科廣為認可和使用的重要最佳化模型。矩陣最佳化問題具有內容新、涵蓋面廣、理論豐富、難度大、套用背景廣泛等特點。部分矩陣最佳化問題和我國“十二五”規劃中提到的一些重點發展領域和目標，如生命科學、信息網路、新型材料、納米科技以及建設資源節約型社會，有著密切的聯繫。在大數據時代，矩陣最佳化模型將成為分析大數據最有力的工具之一，而矩陣最佳化算法的優劣將直接決定人們使用數據、分析數據的能力。 在本項目資助下，我們開展了關於研究矩陣特徵值、奇異值分解；非線性特徵值問題；矩陣低秩分解這三類矩陣最佳化問題的理論及在大數據背景下的套用研究，取得了一些振奮人心的結果。具體研究成果概括為如下三個方面：我們根據不同套用背景下特徵值問題目標矩陣的不同特性，找到相對應的計算瓶頸，針對具體的瓶頸問題，設計新的算法克服這些問題，我們設計的矩陣奇異值分解的軟體包性能穩健；矩陣完整化與主成分分析等矩陣低秩最佳化問題是稀疏最佳化問題的一個重要組成部分，在本項目中我們分析了對於非凸的稀疏最佳化問題的交替方向算法的收斂性；非線性特徵值問題是材料計算中的關鍵問題，求解非線性特徵值的自洽場疊代算法是求解非線性特徵值問題最基本的算法，然而收斂性卻是未知的，我們系統分析的自洽場疊代算法，給出了自洽場算法收斂性的條件，比已有結果更強、具有更廣泛的適用性。 總之，在本項目的資助下，我們完成了申請項目時的既定目標。將來我們會在基金委其它項目的資助下，對矩陣最佳化這一主題繼續探索下去，為我國的最佳化科研事業添磚加瓦。