【作者】 田苗；

【导师】 刘红卫；

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

【摘要】 半定规划是线性规划的一种推广。近年来其理论和算法取得了很大的进展,并且在组合优化、系统工程和电子工程等领域得到了广泛的应用,已经成为数学规划领域中一个非常活跃的研究方向。本文首先介绍了半定规划的理论、算法、研究现状和意义,然后引入了求解半定规划问题的非内点光滑化方法。本文的主要工作包括以下三个方面:1.利用光滑熵函数对半定规划的最优性条件进行转化,得到与其等价的光滑方程组,并应用牛顿法求解该方程组,从而构造了求解半定规划问题的一种光滑化方法。对算法的可行性和收敛性进行了理论分析,并通过数值实验验证了算法的有效性。2.将光滑熵函数中的光滑参数看作独立的变量求解,构造了一种新的算法。证明了算法的全局收敛性和在合适条件下的局部超线性收敛性,并通过数值实验验证了算法的有效性。3.通过改进迭代点及参数的更新方法,减少了求解线性方程组的次数,构造了求解半定规划问题的一种崭新的算法,提高了算法的执行效率。理论分析和数值结果均表明该算法比已有的相关算法优越。更多还原

【Abstract】 Semidefinite programming (SDP) is an extension of linear programming. In recent years, the theory and algorithm for SDP have developed greatly, and its numerous applications are found in combinatorial optimization, system engineering and electrical engineering. SDP is a very important research field in mathematical programming.In this paper, we first summarize the theory, algorithm, research state and significance of SDP. Then, a non-interior smoothing method is proposed for solving the SDP problems. The main work includes the following three aspects:1. The equivalent smoothing equations of the optimal condition are obtained by exploiting the smoothing entropy function. Applying Newton’s method to solve the equations, a smoothing method for the solution of SDP is derived. The feasibility and convergence of the algorithm are analyzed theoretically. Some numerical results are also included which indicate that the proposed method is efficient.2. By regarding the smoothing parameter of the smoothing entropy function as a independent variable, a new algorithm is proposed. The method is shown to be globally and locally superlinearly convergent under suitable assumptions. Numerical experiments show that the method is efficient.3. Through improving the update methods of iterative points and parameters, the number of solving linear equations is reduced and a new method for solving SDP problems is derived. Theoretical analysis and numerical results are included which show that the method is very promising and comparable to several correlative methods.更多还原