秩約束半定規劃問題的算法研究

《秩約束半定規劃問題的算法研究》是依託北京理工大學，由李慶娜擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：秩約束半定規劃問題的算法研究
• 依託單位：北京理工大學
• 項目負責人：李慶娜
• 項目類別：青年科學基金項目

項目摘要

本項目旨在研究秩約束半定規劃問題的算法。該問題源於組合最佳化、金融分析與預測、機器學習、數據挖掘、控制論等多個套用領域，是一類重要的非凸最佳化問題。此類問題非凸性體現在秩約束條件，因此如何處理秩約束十分關鍵。本項目將擺脫傳統求解鬆弛問題的思路，擬採用等價轉化-算法設計的思路，研究秩約束條件，建立等價問題並設計算法直接求解。理論上，我們將借鑑國際上研究五類特殊雙曲錐的思路，探討如何恰當描述秩約束條件，建立問題的等價形式並研究其對偶性質。算法上，有針對性地設計算法，分析算法的計算複雜性及局部收斂速度。在國際上，設計算法直接求解該類問題的研究工作正處於起步階段。據我們所知，目前國內還沒有從直接求解的角度對該問題進行研究的相關工作。因此，開展本項目的研究可以進一步豐富我國在最最佳化理論與算法方面的研究工作，具有重要的研究意義。

結題摘要

項目研究了秩約束半定規劃問題及相關的低秩矩陣最佳化問題及套用，主要成果如下：（1）對於譜範數意義下的帶有等式約束和對稱半正定約束的矩陣逼近問題，利用譜範數函式的Moreau-Yosida正則化性質，提出了交替方向算法求解，數值實驗表明該算法可快速有效地求解快速分配線性平均問題和最優相關係數矩陣逼近問題；（2）在求解實際問題方面，研究了廣域雷達系統中的地面動目標檢測問題，提出了結構化RPCA模型和行模RPCA模型來更好地描述該問題，並設計了基於交替方向思想的算法求解兩個模型。數值模擬結果表明，兩類模型具有更好的地面動目標檢測效果。（3）對地面動目標檢測問題，從理論上研究了該問題的適定性，證明了在三個及以上等間距分布通道的情形下，該問題是適定的，為建立模型和設計算法提供了有力的理論支撐。提出了基於相位的RPCA模型，該模型可以精確刻畫地面動目標檢測問題，並設計了基於交替方向思想的算法進行求解。數值模擬結果表明，該模型較已有模型具有更好的檢測效果。（4）對帶有Schatten-p正則項的矩陣最小二乘問題，建立了其最優解的非零奇異值的下界理論，刻畫了問題的一階和二階必要性條件，並研究了其對應的光滑化問題的相關內容。提出了光滑化梯度算法求解原問題，並將非零奇異值的下界理論用於算法設計中。數值實驗表明，建立的下界理論可以有效地幫助我們得到更稀疏的解。（5）對相位提取問題，提出了基於小波框架的模型，並藉助交替方向的思想設計算法進行求解。數值實驗表明所提算法和已有算法不相上下。 本項目共發表學術論文2篇，SCI收錄1篇，已投稿3篇。 項目申請人在國際重要學術會議上做報告3次，包括大會報告1次，分組報告兩次；在國內重要學術會議上做報告2次，包括大會報告1次，分組報告1次。項目申請人出境學術交流1次2個月，邀請境外專家來訪2人次。