《大規模無約束{-1,1}二次規劃的快速算法及其工程套用》是依託西安電子科技大學，由穆學文擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：大規模無約束{-1,1}二次規劃的快速算法及其工程套用
- 項目類別：青年科學基金項目
- 項目負責人：穆學文
- 依託單位：西安電子科技大學
中文摘要,結題摘要,
中文摘要
無約束{-1,1}二次規劃是組合最佳化領域中一個關鍵問題，它廣泛地套用到通信工程，電子工程，圖像處理等領域。本項目通過對無約束{-1,1}二次規劃的數學結構的分析，利用目標函式的海塞矩陣的稀疏性，分塊方法，低秩分解，譜分解以及可行域的結構，為大規模無約束{-1,1}二次規劃設計快速算法。主要包括錐規劃鬆弛算法和啟發式算法。研究低秩稀疏的半定規劃鬆弛算法和高近似界的二次錐規劃鬆弛算法。結合數據預處理、局部搜尋方法以及模擬退火方法等，設計有效的基於線性規劃的啟發式算法。把設計的快速算法套用到極大似然多用戶檢測、離散係數濾波器設計和圖像分割，二值圖像恢復等問題中。並且結合工程問題的最佳化模型結構，改進現有模型，建立新模型，套用快速算法解決大規模工程問題，通過對實際問題的仿真實驗驗證算法的有效性。項目的成果將推動組合最佳化算法的發展，拓寬組合最佳化在工程問題中的套用領域。
結題摘要
無約束{-1,1}二次規劃是組合最佳化領域中一個關鍵問題，廣泛地套用到通信工程，電子技術與圖像處理等領域。項目分別從結構分析、算法設計以及套用方面進行了研究，成果基本符合預期。在算法設計方面，設計了大規模無約束{-1,1}二次規劃的幾種快速的一階算法，效果較好。在套用研究方面，把設計的快速算法套用到多用戶檢測、離散係數濾波器設計以及圖像處理問題中。具體成果如下：1. 基於無約束{-1,1}二次規劃的半定規劃鬆弛，對矩陣變數利用秩2矩陣近似，得到新的非線性規劃模型，新模型降低了半定規劃鬆弛的規模。利用可行方向法求解該模型，結合隨機擾動算法，得到了問題的近似最優解。實驗結果顯示：秩2半定規劃鬆弛算法與半定規劃內點算法得到的近似最優解性能基本一致，但是我們算法遠遠少於內點算法花費的時間。2. 二階錐規劃鬆弛是無約束{-1,1}二次規劃的一種較低規模的鬆弛方法，基於變分不等式框架，設計了二階錐規劃的幾種一階快速算法。主要成果包括：基於二階錐規化的增廣拉格朗日函式，利用可分離變數結構，提出了交替方向算法，該方法採用並行策略，降低了問題的規模。實驗結果顯示：我們的算法求解一些公開測試問題花費較少的計算時間；另外，基於二階錐規劃的變分不等式的等價形式，設計了一種投影收縮算法，該算法簡單有效。3. 將多用戶檢測問題的{-1,1}二次規劃鬆弛為連續最佳化模型，利用可行方向算法求解該模型，通過啟發式算法得到原問題的近似最優解。該方法將離散問題連續化，連續鬆弛模型的規模遠遠小於半定規劃鬆弛模型的規模。實驗結果顯示，該算法在時間上優於半定規劃鬆弛算法；另外，對多用戶檢測問題，基於半定規劃鬆弛模型，建立其增廣拉格朗日函式，利用交替方向算法求解。該方法降低了問題的規模，在計算時間上相比內點算法有較大的優勢。同時，秩2半定規劃鬆弛和連續化鬆弛算法套用到離散係數濾波器設計問題。4. 對圖像處理問題，利用基於核函式的二階電報擴散方程和高階擴散方程，設計對應的圖像去噪算法。實驗結果顯示：設計的算法在圖像去噪和邊緣保護方面效果要優於已有的去噪和邊緣保護算法。研究結果對大規模無約束{-1,1}二次規划算法的研究有重要的促進作用，在我國信息科學領域中具有廣泛的套用前景。
