论文部分内容阅读
半定规划是线性规划的一种推广,是在满足约束“对称矩阵的仿射组合半正定”的条件下使线性函数极大(极小化)的问题,这个约束是非线性的,非光滑的,凸的[1][2][3][4]。半定规划之所以引起人们广泛的关注,使越来越多的学者投入进来,主要源于两个方面：一是半定规划拥有广泛的应用领域,例如组合优化[5]、统计学、结构设计、电子工程6(滤波器的设计和移动通信)等；第二是因为线性规划的内点算法成功的推广到了半定规划上,并且随着研究的日益成熟,半定规划的内点算法的性能也是越来越良好,而且已经证明内点算法是求解中小规模问题的可靠的有效的算法[7][8]。这对于半定规划的研究具有重要的理论意义和应用价值。半定规划近几年来在算法领域得到了广泛的研究,为NP-hard问题设计多项式时间内的近似算法提供了一种新的思路,并且具有良好的近似性能比。通过研究生期间的研究,应用这种思想,分别针对顶点覆盖问题[8],环状基因排列问题设计了两种多项式时问内的近似算法。在论文中,首先概述了半定规划的内容,对其基本的定义和公式进行了简要的介绍,并且根据半定规划作用的定义域不同,将其分为了实数半定规划SDP和复数半定规划CSDP,论证了SDP和CSDP可以相互转换,而且等价。在导师朱大铭教授的指引下,分别应用此方法对两个NP-hard问题进行了分析：应用SDP随机算法思想对组合优化中的顶点覆盖问题设计了一个多项式时间内的近似算法,近似性能比为2；应用CSDP思想针对环状基因排列问题设计了另外的一个多项式近似算法,近似性能比为4+π/8,是目前为止针对此问题最好的近似算法半定规划随机算法的良好特性,在组合优化的领域将会得到越来越多的关注,并且会吸引算法领域更多的学者对其进行研究。