半定规划是线性规划的一种推广,近年来其理论和算法取得了很大的进展,并且在组合优化,系统工程和电子工程等领域得到了广泛的应用,已经成为数学规划领域中一个新的活跃的研究方向。 本文首先介绍了半定规划的基本知识,包括半定规划的理论与算法,应用和研究现状,然后在半定规划的算法和应用问题方面做了一些工作,具体如下: 1.将半定规划的最优性条件转化成变分不等式,通过求解变分不等式得到求解半定规划的一个新的投影算法,并给出了该算法的收敛性证明。数值实验表明了该方法的有效性。 2.给出了图的最大二等分问题的整数规划模型的等价模型及其新的半定规划松弛模型,利用低秩非线性规划算法求解该半定规划松弛模型,然后利用随机扰动算法求得原问题的次优解。数值实验表明该方法可以有效地求解大规模的图的最大二等分问题。 3.借助于凸分析,非光滑分析等数学工具,从理论上对于特征值优化问题进行了研究,这些有助于求解此类问题。