《無線網路資源分配問題的最佳化算法與複雜性研究》是依託上海大學，由徐姿擔任項目負責人的青年科學基金項目。
基本介紹
- 中文名：無線網路資源分配問題的最佳化算法與複雜性研究
- 項目類別：青年科學基金項目
- 項目負責人：徐姿
- 依託單位：上海大學
中文摘要,結題摘要,
中文摘要
無線網路資源分配是信息通訊和最佳化交叉領域國際研究的新興熱點問題，是下一代通訊網路的關鍵技術，吸引了大批專家學者的極大研究興趣。本課題的研究具有重要的理論價值和廣泛的套用前景。由於這是新興研究方向，有許多重要而又難度大的問題仍未解決，某些理論和算法均亟待進一步研究。本項目主要研究：新型頻譜分配模型的充分最優性條件和最優解的結構；合理模型轉化後，探討新模型所對應的半定規劃鬆弛(SDR)問題對偶間隙為零的充分條件；改進Water-filling算法，設計穩健的波束形成算法，進行複雜性分析；推廣連續化算法的思想，用一系列凸問題來逼近非凸問題來求解波束形成問題，並推廣到一般非凸二次約束二次規劃問題的求解。改進SDR技術中的捨入技巧，並分析新的技巧下SDR問題解的近似比；進一步結合連續化算法和隨機近似算法的思想，研究求解含PIPC或AIPC約束的頻譜分配與功率控制模型的有效算法這一公開問題。
結題摘要
本項目主要針對無線網路資源分配這類新興熱點問題展開廣泛而深入的研究，取得很好的研究成果。（1）針對包含聯合準入控制與波束形成問題在內的兩類特殊的混合0-1二次約束二次規劃模型，提出了兩種不同的半定規劃（SDP）鬆弛方法，證明了等價性；並利用巧妙的捨入技巧，首次得到了該問題的近似算法。該項成果的論文發表在國際頂級最佳化雜誌：SIAM Journal on Optimization上。（2）針對聯合用戶分組與波束形成這一無線通信領域熱點研究問題，提出了新的混合0-1二次約束二次規劃模型,給出了複雜性分析，從理論上證明了一般情形下該問題是NP-難的，並基於SDP鬆弛給出了穩健的波束成形算法。該項成果的論文發表在國際頂級無線通信雜誌：IEEE Journal on Selected Areas in Communications上。該項成果獲得2013年上海市運籌學會舉辦的運籌學青年學者與博士學術論壇優秀論文二等獎。（3）提出了多項組合方向的、雜交的、基於仿真的組合方向3種新的隨機近似算法，並分析了相應的收斂性和漸近收斂速度。（4）關於SDP鬆弛問題的捨入技巧方面的研究也取得了進展。針對disjoint 2-catalog segmentation問題，我們利用新的分析技巧，得到近似比為0.7469的近似算法。此外，在近似算法、一階最佳化方法等方面，我們均取得了一些好的研究成果。
