《基於秩一近似的大規模矩陣最佳化算法及其套用》是依託華南理工大學，由袁淦釗擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：基於秩一近似的大規模矩陣最佳化算法及其套用
- 項目類別：青年科學基金項目
- 項目負責人：袁淦釗
- 依託單位：華南理工大學
項目摘要,結題摘要,
項目摘要
矩陣最佳化算法在圖像處理、機器學習和數據挖掘等諸多領域中有著廣泛的套用。然而，當前最具代表性的矩陣最佳化算法卻是基於特徵值分解，當問題規模很大時這仍然是一項非常耗時的操作。有鑒於此，本課題採用秩一近似策略和局部快速搜尋技術來開展大規模的矩陣最佳化算法的研究。這種算法最顯著的優點就是能夠避免特徵值分解。總的來說，本課題研究內容包括（a）採用秩一近似方法求解無約束矩陣最佳化問題；結合交替方向法求解一般約束的矩陣最佳化問題（b）進行對有約束轉換成無約束問題求解的算法的理論分析，其中包括無約束子問題的最優性條件與精度控制的分析，以及主問題收斂性質與疊代複雜度的分析（c）把該矩陣最佳化技術拓展到其他的科學計算問題上（如帶低秩約束的矩陣最佳化問題），以及拓展到數據挖掘的套用問題上（如差分隱私問題）。.最後，我們對新算法編寫代碼和數值實驗，該成果不僅能豐富矩陣最佳化的理論，而且還為工業界提供一種實用有效的矩陣計算工具。
結題摘要
在本項目中，我們主要從在算法設計、理論分析以及實際套用幾個方面討論了矩陣最佳化問題。我們主要的研究進展、重要結果、關鍵數據以及科學意義情況主要包括以下六點： (a) 低秩最佳化。我們提出了一個高效而且收斂的半正定低秩最佳化方法，該方法能夠精確地求解原來的秩最佳化問題，我們把它用在感測器網路定位上並取得較好的精度。 (b) 差分隱私最佳化。我們提出了一個差分隱私約束下的快速準確的矩陣低秩最佳化模型，該模型可以實現對批線性查詢的最佳化。此外，由於高斯噪音有著旋轉不變性的特性，我們提出一個半正定凸最佳化方法來求解線性差分隱私最佳化問題，該方法在沒有數據先驗前提下取得最好的精度，在不違反用戶隱私前提下提供數據的最大有用性。 (c) 複合函式最佳化。我們提出矩陣分塊策略來求解複合函式最佳化問題和多塊複合函式最佳化問題，這些方法都是線性系統經典方法高斯賽德爾算法或坐標下降方法的拓展。我們把這些方法套用到壓縮感知和矩陣分解問題上，大量實驗表明我們的方法取得了最好的精度和最快的速度。 (d) 稀疏最佳化。我們把脈衝噪音去除過程建模為一個L0范的最佳化問題並提出一個互補約束的交替方向法來求解。此外，我們拓展了這項工作來求解廣義稀疏約束最佳化問題，提出精確罰函式方法和自懲罰交替方向法並且嚴格證明算法的收斂性。 (e) 離散最佳化。我們把一個(-1,+1)離散最佳化問題規約為一個等價的雙線性雙凸問題並提出一個精確罰函式來求解來求解密集子圖發現問題。此外，我們進一步系統地完善了我們之前提出的互補約束最佳化方法並提出自懲罰的交替方向乘子法。 (f) 分解方法。我們把一個稀疏或離散的非凸最佳化問題分解為許多小規模的子問題，此後通過使用全局最佳化的非凸最佳化方法從而實現近似地求解原來的非凸NP難問題。我們證明了算法的收斂性和收斂速度。
