非凸二次最佳化的Lagrangian對偶理論與套用

《非凸二次最佳化的Lagrangian對偶理論與套用》是依託北京航空航天大學，由夏勇擔任項目負責人的面上項目。

基本介紹

• 中文名：非凸二次最佳化的Lagrangian對偶理論與套用
• 依託單位：北京航空航天大學
• 項目負責人：夏勇
• 項目類別：面上項目

項目摘要

考慮NP-困難的非凸二次最佳化，基於原問題與其Lagrangian對偶問題的關係，本項目從等、商、差三大方面展開非凸二次最佳化的Lagrangian對偶理論和套用研究。第一，等號意味著強對偶，即沒有對偶間隙。非凸二次最佳化強對偶的理論基礎是擇一性理論。我們志在推導非齊次Finsler定理，進一步統一兩個一般非齊次二次函式系統的本質的擇一性理論。第二，假定原問題為極大化且最優值大於0，根據弱對偶定理，原問題與對偶問題最優值的商總是小於等於1，本項目延續長期以來的國際研究熱點：深入估計該商的下界，一個副產品是能同時提供原問題的近似算法。第三，在極小化的原問題與其對偶問題最優值之差大於0時，本項目深入發展縮減對偶間隙的技術。本項目中涉及的套用問題包括廣義信賴域子問題、魯棒最小二乘、多球交集的切比雪夫中心近似、加權最大最小分散問題、稀疏主成分分析、二次指派問題等。

結題摘要

本項目按計畫圍繞等、商、差三大方面對非凸二次最佳化的Lagrangian對偶理論和套用展開研究，在Lp球約束極大極小散度問題、預算約束0-1二次規劃、雙井勢函式、p正則子問題、線性兩比式和問題、矩陣線性比式和問題、極大化兩個Rayleigh商之和的最佳化問題、Tikhonov正則化整體最小二乘問題、單一雙邊二次約束的分式二次最佳化問題、二次分配問題、GPS定位問題、兩橢球交集的Chebyshev中心問題、球面上極大化二次型函式的平方和、線性互補約束二次規劃問題、機組組合等問題上取得卓有成效的進展，解決了一些公開問題，提出了新的科學問題，也設計了創新性的全局最佳化算法。其中GPS定位問題的模型和算法以及機組組合問題有望成果轉化。項目整體執行情況良好，完成了既定的研究目標，總計發表期刊論文30篇和會議論文1篇， 其中23篇SCI（待）檢索，包括一篇最佳化頂級期刊Mathematical Programming和兩篇最佳化頂級期刊SIAM Journal on Optimization論文。本項目共資助培養博士研究生畢業4名，碩士生畢業5名，在讀博士生12名。本項目主持人2018年獲批國家自然科學基金優秀青年科學基金項目。