《二階錐約束在非凸二次最佳化問題中的研究》是依託浙江大學，由金慶偉擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：二階錐約束在非凸二次最佳化問題中的研究
- 依託單位：浙江大學
- 項目負責人：金慶偉
- 項目類別：青年科學基金項目
項目摘要,結題摘要,
項目摘要
非凸二次最佳化模型在許多領域都有廣泛套用，但其本身是NP難問題，求解較為困難。將其升維後鬆弛為線性錐最佳化問題是研究該問題的重要研究方法。為了改善鬆弛問題的下界，傳統上主要採用引入有效線性約束、半定約束等方法。研究表明，在鬆弛問題中引入秩2-二階錐約束能有效改善所得下界。二階錐約束線上性二階錐最佳化、凸二次最佳化問題研究較多，但在非凸二次最佳化問題中尚處於不充分。本項目擬從秩2-二階錐約束的生成技術、在新鬆弛問題中的理論分析、非凸二次最佳化問題基於秩2-二階錐約束的算法分析與設計展開研究。具體內容包括：探討秩2-二階錐約束生成技術；建立秩2-二階錐約束在鬆弛問題中的理論基礎；識別多項式可計運算元類問題；比較新方法與現有方法所得下界；針對一些非凸二次最佳化問題的特點設計或改進求解算法，從而為求解非凸二次最佳化問題提供新的思路與高效算法
結題摘要
非凸二次最佳化模型在許多領域都有廣泛套用，但其本身是NP難問題，求解較為困難。將其 升維後鬆弛為線性錐最佳化問題是研究該問題的重要研究方法。為了改善鬆弛問題的下界，在理論分析上，我們研究了包括二階錐約束在內的更廣泛的錐約束下非凸二次最佳化問題解的全局最優性條件，引入非負二次函式錐表達形式，從而提供原問題的等價表達以及更緊的鬆弛形式。在算法設計上，我們探討了如何利用非負二次函式錐表達形式來逼近非凸二次最佳化問題，並利用二階錐約束及其等價形式設計了一系列逼近算法，用來求解不同約束下的非凸二次最佳化問題。此外，我們還針對目標函式海森矩陣負特徵根對目標函式的影響建立相應的等價表達形式和鬆弛問題，並利用該等價表達式設計了高效的分枝定界算法。我們通過數值實驗說明了上述算法相比目前已有算法具有顯著地優勢。在套用方面，我們研究了基數約束下資產投資組合選擇問題，通過一系列等價變化，可以將該問題轉為帶有二階錐約束的非凸二次最佳化問題，從而可以利用前面的結果設計算法進行求解。數值試驗表明，我們的算法在求解這類問題時可以快速有效的逼近最優解。
