大規模半定規劃問題的信賴域算法研究

《大規模半定規劃問題的信賴域算法研究》是依託華中科技大學，由黃愛群擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：大規模半定規劃問題的信賴域算法研究
• 項目類別：青年科學基金項目
• 項目負責人：黃愛群
• 依託單位：華中科技大學

項目摘要

半定規劃問題是線性規劃問題在組合最佳化中的重要推廣，在最優控制論、工程最佳化和模式識別等實際問題中有廣泛的套用。對大規模半定規劃問題的算法及其相關理論的研究，不僅有重要的理論意義，而且也有非常重要的實際套用價值。.　　傳統求解大規模半定規劃問題的算法受到大型對稱矩陣複雜數值計算的限制，算法設計過程中僅僅利用目標函式及其一階導數（梯度）信息，導致精度不高。本項目擬基於過濾技巧和子空間方法，通過將大型實對稱矩陣稀疏化，利用Lipschitz條件和Frechet-導數，研究將高維的大規模半定規劃問題轉化到一個低維子空間中求解。主要研究內容包括：（1）研究大規模半定規劃問題的過濾信賴域算法、子空間信賴域算法以及將過濾技巧和子空間方法結合起來的過濾-子空間信賴域算法；（2）將算法套用到最優控制論和模式識別等實際問題，並依據實際套用效果對算法進行改進和完善。.

結題摘要

半定規劃問題是一類非光滑的凸最佳化問題，理論上可以用凸最佳化的方法求解，但實際求解中因為很難用代數的方法表示約束條件中的矩陣不等式，以及半定規劃問題與其對偶問題的對偶間隙的可能不存在性，使得求解凸最佳化問題的傳統算法（如牛頓法、原始-對偶法等）對半定規劃問題是無效的。 本項目在半定規劃問題及其對偶問題滿足Slater 條件下，給出半定規劃問題及其對偶問題的最優性條件，研究求解半定規劃問題的信賴域算法。根據半定規劃問題的結構特點，利用過濾技巧，一方面避免了罰參數的選取；另一方面放寬了新疊代點的接受準則，由此得到的非單調信賴域算法在理論方面具有最優逼近。同時在此基礎上，考慮到半定規劃問題數據大、變數多的特性，藉助子空間方法，將信賴域子問題轉化到一個低維問題上進行求解，然後回代到原問題中，以減少存儲量和計算量，提高算法的運行速度，進一步完善和改進半定規劃問題的信賴域算法。