半定规划及其应用

半定规划，特别线性半定规划，线性规划的一种推广，是在满足约束“对称矩阵的仿射组合半正定”的条件下使线性函数极大(极小)化的问题，这个约束是非线性。非光滑、凸的，因而线性半定规划是一个非光滑凸优化问题。近十几年内，半定规划已成为数学规划领域中一个非常活跃的研究方向。半定规划之所以引起人们如此大的兴趣主要源于两方面的原因：第一，半定规划有广泛的应用领域，例如在统计学、结构设计、电子工程(滤波器的设计和移动通信等)、组合优化等领域的应用；第二，线性规划的内点算法被成功地推广到半定规划上，使半定规划的内点算法日趋成熟，并且已证明内点算法是求解中小规模问题的可靠有效算法，这对半定规划的研究具有重要的理论意义和应用价值。正如Overton所述：“对半定规划的研究不仅在现在，而且在将来的一段时间里都是一个引人关注的方向，我们可以在这一领域内得到精妙的结果，有效的算法以及广泛的应用。”本文首先概述了线性半定规划的理论。主要算法和半定规划的研究现状，其次是本人攻读博士期间，在导师刘三阳教授的指导下关于半定规划的理论和应用所做的一些工作，具体内容如下： 1．提出了{-1，1}二次约束二次整数规划的强化半定规划松弛模型。和已有的半定规划模型相比该模型能为原问题提供更强的界，并将该模型应用到最大割问题、二次背包问题中，数值实验表明该方法是非常有效的，特别对具有非负权的随机完全图的最大割问题，强化半定规划松弛模型往往会提供原问题的最优解。同时还研究了强化半定规划松弛模型可行域的性质，特别在最大割问题中通过举例和证明得出了比较好的结果。 2．提出了{0，1}线性约束二次整数规划的半定规划定界技术，导出了非线性半定规划模型，同时设计了该非线性半定规划模型的谱向量丛算法，并应用到二次背包问题中，数值实验表明该定界技术是非常有效的，利用该技术在一定规模下能有效地求解二次背包问题，限制迭代次数后会给出二次背包问题很好的次优解。最后，利用半定规划定界技术的思想，提出了最大割问题基于半定规划的二次规划松弛模型。数值实验表明以该二次规划松弛模型为基础，利用分枝定界技术在一定规模下能有效地求解最大割问题。 3．发展了Samuel Burer和Renato D. C. Monteiro对图的最大割问题及最大二等分问题提出的秩2半定规划方法。对{-1，1}二次整数规划问题提出了秩2半定 规划松弛模型.研究了该模型的性质，利用该性质设计了{--幼}二次整数规划问题的 启发式算法，并将它分别应用到CDMA极大似然多用户检测问题和离散系数的数字 滤波器的设计中，数值实验表明该方法是解决{-- 1，1}二次整数规划行之有效的方法 之一在CD琳极大似然多用户检测问题中，和己有的半定规划方法相比它们的误码 率性能没有明显的差异，都接近单用户的误码率，对远近问题误码率性能也没有明 显的差异，但计算时间远远低于己有的半定规划松弛方法的计算时间.在离散系数 的数字滤波器的设计中，和己有的半定规划方法相比它的误差性能基本一致，而计 算时间也远远低于己有的半定规划松弛方法的计算时间. 4.研究了非线性半定规划的凸性庄要是通过反例否定了Dongyiye关于矩阵 值函数最大特征值凸性的猜想及A.seeger关于长方形矩阵值函数奇异值凸性的猜 想. 5.研究了图的最大二等分问题的半定规划方法，首先提出了图的最大二等分问 题新的{--l，l}二次整数规划模型及图的最大二等分问题新的半定规划松弛模型，利 用该模型设计了图的最大二等分问题的坐标上升算法，并用数值实验说明了该算法 的有效性.其次，对非负赋权图的最大二等分问题利用具有严格可行解的半定规划 松弛模型提出了新的0.699算法，在一定意义上改进Yinyuye的工作.最后，定义了 一类较一般的图，提出了该类图的最大二等分问题的0.488算法，并用例子说明了具 有非负权的图真包含于该类图中.