《0-1二次約束二次最佳化問題的非凸二次鬆弛》是依託中國科學院大學，由鄧智斌擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：0-1二次約束二次最佳化問題的非凸二次鬆弛
- 項目類別：青年科學基金項目
- 項目負責人：鄧智斌
- 依託單位：中國科學院大學
項目摘要,結題摘要,
項目摘要
0-1二次約束二次最佳化問題在許多領域都有廣泛套用，但該問題本身是NP難的，其求解較為困難。傳統方法主要使用凸最佳化問題，如線性最佳化，二階錐最佳化，半正定最佳化等，作為鬆弛問題以獲得下界，但是使用非凸最佳化作為鬆弛問題的研究方法尚未被深入探討過。本項目主要研究0-1二次約束二次最佳化問題的非凸二次鬆弛，擬從非凸二次鬆弛的構造方法、理論性質以及基於非凸二次鬆弛的算法設計展開研究。具體內容包括：尋找更多的多項式時間可解的0-1二次最佳化問題；利用二次重構方法構造非凸二次鬆弛；比較非凸二次鬆弛與凸鬆弛所得下界；設計非凸二次鬆弛對0-1二次約束二次最佳化問題的逼近策略；探索有效不等式的新生成技術及其對非凸二次鬆弛的影響；設計基於非凸二次鬆弛的分支定界算法，並將新算法運用到投資組合選擇問題中，為0-1二次約束二次最佳化問題提供新的求解思路和高效的計算工具。
結題摘要
0-1二次約束二次最佳化問題是數學最佳化領域中的基礎研究問題，在現實中有著廣泛的套用。其全局最佳化算法在理論和實際上都有著非常重要的意義。通過這三年對0-1二次約束二次最佳化問題的鬆弛和全局求解方法的研究，本項目預期目標大部分順利完成。本項目從尋找0-1非凸二次最佳化問題的可解子類出發，研究了多種特殊形式下的非凸二次最佳化問題，發現了用以提升下界質量的各種有效不等式和極割，開發了自適應策略以提升算法的收斂速度，設計了基於可計算非凸二次鬆弛和半正定鬆弛的分支定界算法。此外，我們將新算法運用到項目組合選擇問題，非線性支持向量機二元分類問題以及機組組合問題，並取得了良好的效果。本項目為離散約束下的二次最佳化問題提供了新的理論，求解思路和工具。
