非對稱錐最佳化理論與內點算法及其套用研究

《非對稱錐最佳化理論與內點算法及其套用研究》是依託上海大學，由白延琴擔任項目負責人的面上項目。

基本介紹

• 中文名：非對稱錐最佳化理論與內點算法及其套用研究
• 項目類別：面上項目
• 項目負責人：白延琴
• 依託單位：上海大學

中文摘要

非對稱錐最佳化是決策變數取自非自對偶凸錐與仿射集的交，而目標是線性函式的一類最佳化模型。這類最佳化模型是表示非凸二次規劃和組合最佳化難問題的有力工具。被廣泛套用於數據挖掘和圖像處理等實際問題。非對稱錐最佳化形式上保存了對稱錐最佳化的特點，但本質上，由於約束錐的非自對偶性，直接導致了理論研究和算法設計的難度。本項目旨在系統研究非對稱錐最佳化的理論與內點算法及其套用。針對幾類非對稱錐，分析其結構，利用已知對稱性和結構的凸錐來逼近或表示它們；建立代數系統來刻畫錐所誘導的矩陣不等式；建立定義在錐內部的自協調障礙函式，估計障礙參數與維數的關係；設計基於自協調障礙函式的原始或對偶障礙內點算法；分析算法的收斂性和有效性。套用上，將非對稱錐最佳化套用於數據挖掘和圖像處理的建模與算法中，特別為分類問題提供可計算的錐最佳化模型和最佳分類機。本項目的研究目標是突破約束錐在非自對偶的情形下帶來的困難，豐富和發展錐最佳化理論與方法。

結題摘要

本項目主要探索和研究非對稱錐最佳化的理論與內點算法及其套用。眾所周知，非對稱錐最佳化是決策變數取自不自對偶的凸錐與仿射空間的交集和目標函式是線性函式的一類最佳化模型。這類最佳化模型是表示非凸二次規劃和組合最佳化NP難問題的有力工具，被廣泛套用於數據挖掘、機器學習中的分類模型、圖像處理、稀疏最佳化等實際問題。本項目系統與具體開展了五個方面的研究內容:1.關於非對稱旋轉錐最佳化模型與內點算法。2. 錐最佳化模型與有效算法在機器學習中分類問題的套用。3.高次非齊次多項式和複數多項式最佳化問題的近似算法。4.稀疏約束和半連續約束最佳化問題的分裂拉格朗日方法。5.關於帶有敏感參數的投資組合問題的模型與算法及其套用。在五個研究方向中，項目分別做出一系列具有一定創新性和先進性的研究工作，取得了豐富的研究結果。比如發展了非對稱協正錐、非對稱旋轉錐的代數表達理論和自協調函式理論，設計了非對稱旋轉錐的具有多項式時間的內點算法；分別為機器學習中分類問題和回歸問題構建錐最佳化模型；並設計一階與內點算法等快速算法求解實際的分類問題和回歸問題；分析了四階張量錐性質及希爾伯特恆等式分解；推廣了張量Tucker分解最優核選擇及其套用；設計了求解稀疏約束和半連續約束最佳化問題的分裂拉格朗日方法，在圖像處理高維數據的套用中具有顯著的效果。在套用方面，對於實際疾病分類問題，選取了國際通用資料庫(UCI Repository) 的實際算例進行了數值試驗. 數值結果分別表明，研究工作提供的最佳化模型與算法具有好的分類和聚類效果。 本項目五個研究方向的先進性、研究內容的創新性以及研究結果的前沿性與豐富性，項目的研究工作產生的影響力體現在豐富和發展了錐最佳化的理論與算法。項目的研究成果以論文的形式體現，總共發表了28篇期刊論文，其中4篇文章發表在最最佳化領域頂級期刊Mathematics of Operations Research；計算數學的頂級期刊Foundations of Computational Mathematics和Mathematics of Computation和國際信號處理頂級期刊IEEE Transactions on Automatic Control.在項目的支持下，培養了運籌學與控制論專業的8名博士研究生和9名碩士研究生。