《大規模矩陣錐約束最佳化問題的理論、算法及其套用》是依託北京工業大學，由趙欣苑擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：大規模矩陣錐約束最佳化問題的理論、算法及其套用
- 項目類別：青年科學基金項目
- 項目負責人：趙欣苑
- 依託單位：北京工業大學
項目摘要,結題摘要,
項目摘要
大規模矩陣錐約束最佳化問題是最最佳化研究領域中的重要問題之一，在數值最佳化、魯棒最佳化、投資組合最佳化以及統計學理論等領域有著極其廣泛和重要的套用。現有的方法只能處理在對於中小規模的對稱矩陣問題，因此深入研究大規模的矩陣（特別是非對稱矩陣）錐約束最佳化問題的算法及其相關理論和軟體設計有著重大意義。本項目以擾動分析和變分分析理論為基礎，運用投影運算元的方向可微性和強半光滑性，研究大規模部分陣完成問題的半光滑牛頓增廣拉格朗日算法，大規模低秩近似矩陣問題的基於增廣拉格朗日方法的算法，和對於一般閉凸錐約束最佳化問題的增廣拉格朗日方法，並編寫上述算法的matlab軟體。
結題摘要
大規模矩陣錐約束最佳化問題臘遷酷講是最最佳化研究領域中的洪匙府重要問題之一，在數值最佳化、魯棒最佳化、投資組合最佳化以及統計學理論等領域有著駝刪境極其廣泛和重要的套用。該項目主要深入研究了大規模矩陣錐約束最佳化問題中幾類典型模型的理論、算法和套用。 首先，雖然內點算法是牛糠嫌求解半正定規劃問題重要方法之一，但是該算法需要疊代點是問題的嚴格可行點，這在編程實現內點算法時產生了困難。通過增加一個簡單的人工變數，構造出以單位元素I為嚴格可行初始點的半正定規劃問題；並且僅通過求解兩維的半正定規劃問題就可改進構造問題的勢能函式的界值，大大降低了求解的計算量。分別對半正定規劃的原始問題和對偶問題提出的相應的算法，使得最優解能夠同時滿足問題的可行性和最優性條件。我們分析了算法的收斂性和對三種算法的數值實驗結果進行了比較。同時，課題組還討論了組合最佳化問題中的設施選址問題中兩目錄分割問題的半正定鬆弛模型的近似算法。在不相交的情況下，運用不均勻旋轉和半正定鬆弛的技巧，用半正定鬆弛問題的最優解和整個權重的比值來表示性能曲線，此曲線的最低點就顯示了近似比為0.7317和相交2-CSP問題的近似比囑微旋探為0.6338，是目前最好的結果。 接著，研究大規模凸的二次約束二次半正定規劃問題，給出了在原點Lipschitz連續性的等價條件、Robinson約束規範、強二階充分條件、以及約束非退化準則的顯示表達式；並證明了子問題的廣義Hessian矩陣的正定性確保了使用非精確半光滑牛頓-共軛梯度法求解時具有超線性收斂率。在編寫Matlab程式進行數值實驗，利用所提出的半光滑牛頓-共軛梯度增廣拉格朗日方法對魯棒的估計協方差矩陣的數學模型進行了實驗，得到了穩定和有效的數值結果。 項目組成員還共同研究了帶線性耦契約束的極小化可分凸函式與光滑凸函式和的規劃問題。通過利用塊坐標下降方法的超線性收斂性，克服交替方向法對於超過戒鞏捆3個乘子的問題不收斂的缺陷，提出了一個新的替換近似塊乘子極小化算法，並在收縮型方法框架下證明了所提出的算法收斂性，得到了在最壞情況為O(1/K) 收斂率，K是指算法疊代步數。初步的嫌多數值實驗已表明了所提出的算法的有效性。
