【作者】 徐凤敏；

【导师】 刘三阳；

【作者基本信息】 西安电子科技大学 ， 运筹学与控制论， 2001， 硕士

【摘要】 半定规划是线性规划的推广，它是在线性规划中用矩阵变量取代向量变量、用矩阵的半正定性取代向量的非负性而得到的，其约束是非线性、非光滑的，但却是凸的，因而半定规划是凸规划。由于半定规划不仅在系统论、控制论、组合优化、特征值优化等诸多领域中有着广泛的应用，而且使线性规划、二次规划等典型问题成为其特例，近年来备受人们的重视，已成为数学规划领域研究的一个新方向。本文工作包括以下三个方面：1．根据半定规划最优性条件与变分不等式的等价关系，得到求解半定规划的一个 新的投影算法，并给出数值实验和收敛性证明。2．首先将半定规划的摄动最优性条件转化成最小二乘问题，通过求解此问题获得 新的原-对偶搜索方向，即Gauss-Newton方向。并基于此方向给出求解半定规 划的原-对偶路径跟踪算法及收敛性证明，数值实验表明Gauss-Newton方向具 有比其他方向更好的数值稳定性。3．对一些组合优化问题，在已知半定规划模型基础上，通过增加非线性约束，利 用二次提升得到它们的强化半定规划松弛，理论和数值实验表明强化半定规划 松弛给出原问题更好的上界。更多还原

【Abstract】 Semidefinite programming (denoted SDP) is an extension of linear programming(LP), with vector variables replaced by matrix variables and nonnegativity elementwisereplaced by positive semidefinite. It is well known that the constraint of semidefiniteprogramming is nonlinear and nonsmooth , but convex, so semidefinite programming isconvex optimization problems. Semidefinite programming unifies several standardproblems (e.g., linear and quadratic programming) and finds many applications fromsystem and control theory to combinatorial optimization as well as eigenvalueoptimization, so semidefinite programming is viewed as a new and important researchdirection in mathematical programming. This paper consists of there parts:1.A new projection algorithm solving semidefinite programming is attainted by theequivalence of the optimality conditions and the variational inequality. Theconvergence analysis and numerical experiment are also contained.2.We translate the perturbed optimality conditions of semidefinite programminginto the least squares problem, a new primal-dual direction (Gauss-Newtondirection) is achieved by solving the least squares problem. An infeasibleshort-step path-following algorithm based on the Gauss-Newton direction andConvergence analysis are given. The empirical evidence suggests the directionoffer more robust than other directions currently in use.3.The strengthened SDP relaxation is based on applying a lifting procedure to thiswell-know SDP relaxation after adding the nonlinear constraints. It is shown thatthe new bound obtained this way strictly improves the previous SDP boundboth empirically and theoretically.更多还原