【作者】 徐引玲；

【导师】 刘红卫；

【作者基本信息】 西安电子科技大学 ， 应用数学， 2007， 硕士

【摘要】 半定规划是数学规划方面一个相对较新的领域,是线性规划的推广,它是在满足约束“对称矩阵的仿射组合半正定”的条件下使线性函数极大(极小)化问题,这个约束是非线性的、非光滑的、凸的,因而半定规划是一个非光滑凸优化问题。本文首先介绍了半定规划的基本理论、主要算法和研究现状,在此基础上对半定规划问题算法研究做了如下工作:1.给出了解决半定规划问题的筛选算法。文中首先采用低秩分解技术将半定规划问题转化为与其等价的非线性规划问题,进而利用非线性规划问题的筛选算法来求解。文中给出了两种筛选算法,一种是基于方向分解的筛选法,分析了它的主要思想,并给出了具体的算法,最后给出了它的收敛性结论。另一种是与SQP结合的筛选法,对其进行了详细的分析,并得到了较好的全局收敛性结论.2.文中又给出了一种光滑化牛顿方法。首先利用推广的Fischer-Burmeister函数将半定规划问题的KKT条件转化为一个等价的非光滑方程组,进而利用光滑化方法将该非光滑方程组光滑化,构造了半定规划问题的光滑化方法。最后,在超线性收敛的基础上,又对算法作了改进,得到了二次收敛性结论。更多还原

【Abstract】 Semidefinite programming is an extension of linear programming. In semidefinite programming, one maximizes (minimizes) a linear function subject to the constraint that an affine combination of symmetric matrices is positive semidefinite. Such a constraint is nonlinear and nonsmooth, but convex, so semidefinite programming is a nonsmooth and convex optimization problem.In the paper, the theory, algorithm,and recent reseach of semidefinite programming are summarized, some works in algorihm are introduced. In detail, we conclude them as follows:1. A filter method for semidefinite programming is proposed in this paper. Firstly, a low-rank decomposition technique is adopted to transform the standard semidefinite programming into an equivalent nonlinear programming problem. Then two kinds of filter algorithms are introduced to solve the problem. The first algorithm is based on a decomposition of direction. We give the main idea of it and the convergence conclusions. The second is a combination of filter and the SQP. A detailed analysis is carried out and better global convergence conclusions are obtained.2. An extensive Fischer-Burmeister function method are used to convert the optimality conditions of SDP into an equivalent nonsmooth system of equations, then by smoothing the nonsmooth equations, a smoothing-type method for semidefinite programming is constructed. At last, on the basis of the superlinear convergence, an improved algorithm is presented and a rapid quadratic convergence conclusion is obtained.更多还原