含不等式约束的复半定规划的求解及应用

摘要

半定规划作为一种强有力的凸优化技术在各个领域已经得到广泛的应用，展示出了极强的建模复杂问题的能力。近些年来，半定规划在通信领域也逐渐发展起来，研究的主要方向有两个，第一，改进和寻找适合通信领域半定规划问题的算法；第二，使用半定规划建模和仿真工程实际问题。主流的半定规划软件SeDuMi是内点法的典型实现，它在求解大规模问题所需的内存和计算时间远远超过了实际工程所允许的计算资源和能承受的时间代价。本文主要研究正是为了解决上述问题，设计了一种大规模含不等式约束的复半定规划问题的有效求解算法LRF。
　　SDPLR算法在求解含等式的实半定规划问题具有出色的性能和较低的内存需求。主要是其采用了低秩分解的方法，有效的降低了变量的个数，进而降低了问题的规模。通过低秩分解的方法，将含等式约束的实半定规划问题转化为非线性规划问题，并通过增广拉格朗日函数进行优化，同时仿真结果了也显示了低秩分解方法的优越性。
　　通信领域的问题往往被建模为复数域的含大量不等式约束的半定规划问题。SDPLR算法在求解含大量不等式约束的问题需要添加额外的辅助变量，使得急剧增大的问题规模远远超过原始问题的规模而造成严重的性能下降。本文主要工作从以上两点出发，首先在复数域重新推导和修正了低秩分解方法，其次含不等式约束的半定规划问题重新构造的增广拉格朗日函数 ALF是辅助变量的二次函数。固定原始优化变量并求取辅助变量的最优解的代数形式，将辅助变量的最优解带入增广拉格朗日函数形成了需要优化的最小化增广拉格朗日函数 MALF。除此之外，通过使用LBFGS和不精确一维搜索等方法提高大规模问题的计算性能。
　　为了验证 LRF算法和 SeDuMi算法的性能，使用它们分别求解干扰对齐问题。在最优解满足工程需求下，仿真结果显示求解小规模半定规划问题时，SeDuMi的解和运行时间都优于LRF算法。求解大规模半定规划问题时，SeDuMi的运行时间会急剧的增大甚至不能正常求解超大规模问题。而 LRF算法的运行时间比SeDuMi有非常大的优势，并且随着问题规模的增大优势更加明显。

目录

封面

声明

中文摘要

英文摘要

插图索引

表格索引

符号对照表

缩略语对照表

目录

第一章 绪论

1.1选题的缘由和意义

1.2半定规划国内国外的现状

1.3干扰对齐的现状

1.4论文的研究思路和方法

第二章 线性规划和半定规划的基础知识

2.1线性规划的基本概念

2.2半定规划的基本概念

2.3内点法

2.4本章小结

第三章 实半定规划问题的SDPLR算法

3.1实半定规划问题的低秩分解和变形

3.2 SDPLR算法

3.3本章小结

第四章 复半定规划问题的LRF算法

4.1下降方向的计算

4.2一维不精确搜索

4.3复数域SDPI的LRF算法

4.4 LRF算法复杂度分析

4.5本章小结

第五章 干扰对齐问题的仿真

5.1干扰对齐问题的建模

5.2仿真与分析

5.3本章小结

第六章 结论和展望

6.1研究总结

6.2工作展望

参考文献

致谢

作者简介