非負二次函式錐規劃研究

《非負二次函式錐規劃研究》是依託清華大學，由邢文訓擔任項目負責人的面上項目。

基本介紹

• 中文名：非負二次函式錐規劃研究
• 依託單位：清華大學
• 項目負責人：邢文訓
• 項目類別：面上項目

項目摘要

非負二次函式錐規劃是現有的共正錐規劃的擴展，是錐規劃研究的一個新的研究方向,其研究將為經典的非凸二次規劃問題提供新的理論與算法，並從中得到比傳統研究方法更深刻的結果。首先，本項目將深入研究非負二次函式錐的理論性質，並根據其性質，設計可計算的內逼近錐，最終將可計算逼近錐套用於非負二次函式錐規劃問題的逼近算法上。其次，將可計算內逼近錐方法套用在典型二次規劃和組合最佳化等問題，進一步改進半定規劃等方法的下界估計效果。最後，根據問題本身的結構特徵，找到針對某一類問題表現效果更佳的內逼近錐，以更好的計算效果逼近共正規劃問題，以及非負二次函式錐規劃問題。

結題摘要

本項目主要研究二次約束二次規劃（QCQP）問題的性質及其計算方法，主要研究手段是通過線性錐規劃理論的研究，給出QCQP問題的線性錐規劃等價模型，最優性條件和求解全局最優解或近似全局最優解的算法及收斂性分析。主要成果如下:第一，建立了正則對偶方法在最最佳化領域套用的數學理論。針對QCQP問題，我們利用Lagrange對偶的觀點，給出了正則對偶方法的理論結果和在一些最佳化問題中的套用，在理論上給出了利用正則對偶方法如何構建QCQP的可行解，全局最優解的最優性條件和構造全局最優解的計算方法。第二，給出了用非負二次函式錐判斷全局最優解的一個充分條件。通過一個非負二次函式錐的表示，我們給出一個QCQP可行解為全局最優解的一個充分條件。這一結果為我們首次發現，並一直套用在我們後續的研究問題中。由於判斷一個矩陣是否屬於這個非負二次函式錐是一個NP完全問題，後期的工作給出了這個錐的可計算近似表示。第三，系統給出非負二次函式錐的橢球覆蓋和二階錐覆蓋逼近的計算理論與算法。在最優目標值相同的觀點下，QCQP問題可以等價地表示成一個定義域在非負二次函式錐上的線性錐最佳化問題。因該錐的難度而無法多項式時間求解這個線性錐最佳化問題，我們成功地用橢圓或二階錐覆蓋可行解區域的系統方法，求解到任意逼近QCQP最優目標值的近似全局最優解，並給出了系統的理論。近些年的工作已整理並完成專著《線性錐最佳化》，2013年由科學出版社出版基金資助出版。課題負責人多次在國際國內會議上報告與本課題相關的研究成果。據不完全統計，大會邀請報告次數超過6次，標註自然科學基金資助文章19篇、專著1部。在與本課題時間重合期間培養的研究生（已畢業）包括：4名博士生，6名碩士生。