凸可分半定規劃的數值算法

《凸可分半定規劃的數值算法》是依託南開大學，由張蘇擔任項目負責人的青年科學基金項目。

基本介紹

• 中文名：凸可分半定規劃的數值算法
• 項目類別：青年科學基金項目
• 項目負責人：張蘇
• 依託單位：南開大學

中文摘要

凸可分半定規劃是一類在金融、工程等領域具有廣泛套用背景的數學問題。凸非線性半定規劃和大規模矩陣最佳化目前的一些實際套用均可以放在此框架下考慮，該模型也為這些實際問題的進一步研究提供了新的視野。本項目旨在通過分析各種矩陣函式的理論性質研究求解凸可分半定規劃的數值算法。我們首先運用最佳化的思想，將原問題轉換成一個矩陣空間下的變分不等式問題。這樣屬於一階算法的交替方向法可以被推廣用來求解凸可分半定規劃問題。但是由於矩陣錐最佳化的結構特點，必須對原始算法作出適當的改良，以設計出易實現、高效率的實用數值算法。同時對於某些特殊類型的凸可分半定規劃問題，提出相應的簡便算法。最重要的是，改進後交替方向法的全局收斂性必須得到嚴格的數學證明。更進一步，我們還將分析其理論收斂速度以及用實際算例檢驗其數值表現。

結題摘要

在大數據廣泛套用的背景下，凸可分半定規劃屬於一類重要的大規模數據矩陣最佳化問題。我們項目根據矩陣函式的理論性質，提出一些求解凸可分半定規劃的易實行、高效率的實用數值算法。我們還根據實際出現的一些特殊類型問題，設計出相應的簡便算法。為了解決大數據模型，我們將之轉換成變分不等式後，一般使用包括交替方向法在內的一階算法。我們證明了其收斂性，並分析了其收斂速度，更重要的是數值檢驗其計算效果。在項目資助發表的文章中，這些算法被套用來解決Netflix問題、投資組合問題、設施選址問題等重要的實際大數據問題，而且得到了良好的結果。