无线网络资源分配问题的优化算法与复杂性研究

无线网络资源分配是信息通讯和优化交叉领域国际研究的新兴热点问题，是下一代通讯网络的关键技术，吸引了大批专家学者的极大研究兴趣。本课题的研究具有重要的理论价值和广泛的应用前景。由于这是新兴研究方向，有许多重要而又难度大的问题仍未解决，某些理论和算法均亟待进一步研究。本项目主要研究：新型频谱分配模型的充分最优性条件和最优解的结构；合理模型转化后，探讨新模型所对应的半定规划松弛(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的近似算法。此外，在近似算法、一阶优化方法等方面，我们均取得了一些好的研究成果。