半定规划理论与应用：算法优化与分支定界法

"本文详细探讨了半定规划的概念、理论、算法及其实现，以及它在多个领域的广泛应用。作者蒋耀伟在导师刘三阳的指导下，对半定规划的二次规划松弛模型、分支定界法在滤波器设计和图的最大二等分问题中的应用，以及可直接求解的半定规划问题进行了深入研究。" 半定规划是优化理论的一个分支，它是线性规划的一种扩展，允许决策变量包含对称矩阵，且目标函数和约束条件涉及这些矩阵的线性组合和半定性。半定规划的理论基础主要建立在凸优化和矩阵分析之上，其中内点算法的引入极大地推动了该领域的发展，使得半定规划问题可以有效求解。 本文首先阐述了半定规划的基本概念，包括它的定义、性质以及在数学规划中的地位。接着，作者提出了一种基于二次(1,1)规划的半定规划松弛模型，该模型能提供更优的界，并通过分支定界法进行求解。经过理论分析和数值实验，验证了这种方法的有效性和优势。 此外，论文还展示了分支定界法在实际问题中的应用。例如，在离散系数滤波器设计中，分支定界法相较于随机扰动算法能获得更接近最优解的结果，且设计出的滤波器与理想滤波器的误差极小。对于图的最大二等分问题，分支定界法也展现出良好的近似解能力，尤其适用于解决中小规模问题。 最后，论文探讨了可以直接求解的半定规划问题，包括介绍现有的一些可以直接求解的问题类型，并提出一类新的具有特殊约束条件的半定规划问题。这些问题可以通过一系列矩阵变换直接得到最优解，无需传统的迭代方法，从而大大简化了解决过程。 关键词：半定规划，(-1,1)二次规划，分支定界法，直接求解 总体来说，本文为读者提供了关于半定规划的全面理解，不仅涵盖了理论基础，还展示了其实用价值和在不同领域的应用，特别是在优化问题和工程实践中。这些研究成果为半定规划的进一步发展和应用提供了有价值的参考。